導入
atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。
使用しているアルゴリズム
- 0-1 BFS（双端キューによるコスト付きBFS）
解法のポイント
- 移動は上下左右の4方向に可能で、基本的にはBFSで進んでいきます。
- ただし、「壁」を2枚まで前蹴り（＝コスト1）で通過できるため、通常のBFSではなく 0-1 BFS を使います。
-
道（.）を通るときはコスト0で優先的に探索（
appendleft）、壁（#）を通るときはコスト1として後回し（append）にします。 - 前蹴りは2マス先まで有効なので、
i=1,2で2マス分をループで処理。 - 探索先のコスト（
ans[ny][nx]）が、すでにより少ないか同じ回数で更新されていた場合はスキップします。 -
i=1で通れる道があれば、それが最短なのでbreakしてi=2には進みません。 - ゴールに到達した時点で、
ans[goal]に最小の前蹴り回数が格納されます。
ACサンプル
from collections import deque
H,W = map(int,input().split())
INF = H*W
grid = [list(input()) for _ in range(H)]
ans = [[INF]*W for _ in range(H)]
sy,sx,ey,ex = map(int,input().split()) # 1-index
dys = (1,-1,0,0)
dxs = (0,0,1,-1)
dq = deque()
dq.append((sy-1,sx-1)) #0-index
ans[sy-1][sx-1] = 0
while dq:
now = dq.popleft()
# goal座標に到達したら終了
if now == (ey-1,ex-1):
break
y,x = now
current_cost = ans[y][x]
for dy,dx in zip(dys,dxs):
wall = False
for i in range(1,3):
ny = y + dy * i
nx = x + dx * i
if ny < 0 or ny >= H or nx < 0 or nx >= W:
break
feature_cost = current_cost if i == 1 else current_cost + 1
if ans[ny][nx] <= feature_cost:
continue
if grid[ny][nx] == "#":
wall = True
if not wall:
if i == 1:
ans[ny][nx] = current_cost
dq.appendleft((ny,nx))
break
else:
ans[ny][nx] = current_cost + 1
dq.append((ny,nx))
print(ans[ey-1][ex-1])