白駿1987文字

白駿1987のアルファベット問題をやってみましょう.

Pythonコード

N, M = map(int,input().split())
graph = [list(input()) for _ in range(N)]
board = [[False for _ in range(M)] for _ in range(N)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

result = 0

def dfs(r, c, visit, alphabet):
  global result
  count = 0
  alphabet_set = set(visit)
  if board[r][c] != alphabet_set:
    board[r][c] = alphabet_set
    visit.append(graph[r][c])
    for i in range(4):
      new_r = r + dy[i]
      new_c = c + dx[i]
      if new_r < 0 or new_r >= N or new_c < 0 or new_c >= M:
        continue
      if graph[new_r][new_c] not in visit:
        count += 1
        li = visit[:]
        dfs(new_r, new_c, li, alphabet+1)
  if count == 0:  
    result = max(result, alphabet)

dfs(0, 0, [], 1)
print(result)

この問題は複雑だとは思いませんが、タイムアウトを避けるためにいろいろ努力しました.私が考えているアルゴリズムでは、一般的にアルゴリズムを作るだけで、ずっとタイムアウトします.だからグーグルで遊んでいるとき.
Pythonのモジュールコピー.deepcopyがあります.
共有リストを回避するために深さレプリケーションを行ったが,これには長い時間がかかることが分かった.この間、深度コピーが必要になるたびにdeepcopyを利用しています.
このモジュールよりスライド速度がずっと速いそうです.
したがって

li= vistit[:] 

このようにSleingレプリケーションで多くの時間を短縮また,環境が以前計算した環境と同じであれば,再帰関数ですべての状況を検索しないという条件も追加した.
boardという2 D配列を作成し、各座標にアルファベットのset()を配置し、そのアルファベットセットに座標を移動すると、再帰関数が呼び出されず、時間が短縮されます.
また….deepcopyが苦手なため!