[Python] 01-BFS ARC005C

ARC005C

01-BFSのちょっと丁寧な解説

辺の長さが "0" または "1" である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めるアルゴリズムであり、実装には両端キューがよく使われる。
一般的な辺の長さの場合は、ダイクストラ法が適しており、優先度付きキューがよく使われる。

解法

「距離」を「移動コスト」再定義して「通路の移動コストは０」「壁の移動コストは１」とすれば「壁を最大二回移動してゴールに到達できるか」が算出できる。01-BFSの計算量は頂点数を$V$、辺数を$E$とすると$O(V+E)$となり、通常のBFSと同等となる。
Python3でACするが、PyPy3では MLE (Memory Limit Exceeded)となる。

サンプルコード

# 両端キュー(double-ended queue)インポート
from collections import deque
inf=10**9
h,w=map(int,input().split())
s=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
                # スタート地点読込
        if s[i][j]=="s":
            sx=i
            sy=j
                # ゴール地点読込
        elif s[i][j]=="g":
            gx=i
            gy=j
deq=deque([(sx,sy)])            # スタート地点から01-BFS開始
dis=[[inf]*w for i in range(h)] # 距離は無限遠で初期化
dis[sx][sy]=0
d=[(1,0),(-1,0),(0,1),(0,-1)]   # 上下左右
# 01-BFS
while deq:
        # 左端から探索地を取り出す
    x,y=deq.popleft()
    for dx,dy in d:
        if 0<=x+dx<h and 0<=y+dy<w and dis[x+dx][y+dy]==inf: # 境界条件
            if s[x+dx][y+dy]=="#":
                dis[x+dx][y+dy]=dis[x][y]+1
                # 右端に探索地を追加
                deq.append((x+dx,y+dy))
            else:
                dis[x+dx][y+dy]=dis[x][y]
                # 左端に探索地を追加
                deq.appendleft((x+dx,y+dy))
print("YES" if dis[gx][gy]<=2 else "NO")