まずは結論から。
この問題は単純なBFSではなく、「直前の移動方向」も状態に含めて管理する必要があった。
また、Pythonで実装する場合、訪問管理に set() を使うとTLEになるため、3次元配列による定数倍の高速化が必須だった。
コンテスト中に考えたこと
幅優先探索（BFS）または深さ優先探索（DFS）で解けそう。
しかし、前回動いた方向に依存するマス（o や x）がある。
そのため、単純に「一度通ったマスを候補から消す」というやり方はできなさそう。
どうやってそれを解決するか分からず、時間切れ……。
経路復元のやり方についても分からなかった。
解説をみて：状態の持ち方と経路復元
解説を確認して、以下の2点に気づいた。
状態の再定義
位置(y, x)に加えて、「前回進んだ方向」を保持することで、マスの進入制限をクリアしつつ同じ状態を回避できることが分かった。経路復元のアプローチ
別で配列（prevs）を作成し、木構造のようにループ毎に「どこから来たか」と「その向き」が分かればできるはず。
実装としては、queueの探索ごとに配列に現在のノード（親のインデックスと移動方向を含む）を追加してインデックスを増やしていく。そして、キューに追加するタイミングで現在のインデックスも一緒に保持しておくと、ゴールから逆走して「どこから来たか」が辿れるようになる。
失敗
訪問済みの管理は、Pythonでよくやる visited = set() で書いた。以下が当時の省略なしの全コード。
from collections import deque
# 幅優先探索かも
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
start = [0,0]
goal = [0,0]
for i in range(H):
for j in range(W):
if S[i][j] == "S":
start = [i,j]
if S[i][j] == "G":
goal = [i,j]
# 位置と前回動いた方向をセットで状態とし、状態をノードとして幅優先探索をする。
# 状態を(y,x,direction)で定義する
# キューには経路復元用のprev上のインデックスを持たせる
queue = deque([[start[0],start[1],None,None]])
visited = set()
prevs = []
flag = False
index = 0
while queue:
node = queue.popleft()
visited.add(tuple(node[:3]))
prevs.append(node)
if node[:2] == goal:
flag = True
break
cur_y,cur_x,prev_direction,prev_index = node
if S[cur_y][cur_x] in [".","S","G"]:
for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
ny,nx = cur_y+dy,cur_x+dx
if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited:
queue.append([ny,nx,direction,index])
elif S[cur_y][cur_x] == "o":
for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
ny,nx = cur_y+dy,cur_x+dx
if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited and direction == prev_direction:
queue.append([ny,nx,direction,index])
elif S[cur_y][cur_x] == "x":
for (dy,dx,direction) in [(1,0,"D"),(0,1,"R"),(-1,0,"U"),(0,-1,"L")]:
ny,nx = cur_y+dy,cur_x+dx
if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and (ny,nx,direction) not in visited and direction != prev_direction:
queue.append([ny,nx,direction,index])
index += 1
if flag:
print("Yes")
# 経路復元
# prevsのindexからさかのぼる
reversed_path = []
while index != 0:
reversed_path.append(prevs[index][2])
index = prevs[index][3]
path = reversed(reversed_path)
print("".join(path))
else:
print("No")
結果：TLE
状態空間が広いため、ループのたびにタプルを生成し、set のハッシュ値を計算して追加・検索する処理が重すぎたらしい。
ACをするためにやったこと
set をやめて、処理の軽い「配列のインデックスアクセス」に入れ替えた。
方向は4つ（D, R, U, L）しかないので、visited[y][x][方向] を表す3次元配列を用意すればいい。
結果：ギリギリAC！
最終的なACコード
from collections import deque
# 幅優先探索かも
H, W = map(int, input().split())
S = [input() for _ in range(H)]
start = [0, 0]
goal = [0, 0]
for i in range(H):
for j in range(W):
if S[i][j] == "S":
start = [i, j]
if S[i][j] == "G":
goal = [i, j]
# 位置と前回動いた方向をセットで状態とし、状態をノードとして幅優先探索をする。
# 状態を(y,x,direction)で定義する
# キューには経路復元用のprev上のインデックスを持たせる
queue = deque([(start[0], start[1], None, None)])
# setから3次元配列に変更して高速化
visited = [[[False] * 4 for _ in range(W)] for _ in range(H)]
prevs = []
flag = False
index = 0
# (dy, dx, 方向の文字, 訪問配列用のインデックス)
moves = [(1, 0, "D", 0), (0, 1, "R", 1), (-1, 0, "U", 2), (0, -1, "L", 3)]
while queue:
node = queue.popleft()
prevs.append(node)
if node[0] == goal[0] and node[1] == goal[1]:
flag = True
break
cur_y, cur_x, prev_direction, prev_index = node
cell = S[cur_y][cur_x]
for dy, dx, direction, d_idx in moves:
if cell == "o" and direction != prev_direction:
continue
if cell == "x" and direction == prev_direction:
continue
ny, nx = cur_y + dy, cur_x + dx
if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != "#" and not visited[ny][nx][d_idx]:
queue.append((ny, nx, direction, index))
visited[ny][nx][d_idx] = True
index += 1
if flag:
print("Yes")
# 経路復元
# prevsのindexからさかのぼる
reversed_path = []
while index != 0:
reversed_path.append(prevs[index][2])
index = prevs[index][3]
path = reversed(reversed_path)
print("".join(path))
else:
print("No")
Top comments (0)