1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] 01-BFS ARC005C

Last updated at Posted at 2020-12-13

#ARC005C

#01-BFSのちょっと丁寧な解説
辺の長さが "0" または "1" である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めるアルゴリズムであり、実装には両端キューがよく使われる。
一般的な辺の長さの場合は、ダイクストラ法が適しており、優先度付きキューがよく使われる。
#解法
「距離」を「移動コスト」再定義して「通路の移動コストは0」「壁の移動コストは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")
1
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?