[Python] 01-BFS ARC005C


A little polite explanation of 01-BFS

** An algorithm that finds the length of the shortest path from one start point to all vertices in an efficient calculation time in a directed graph with an edge length of "0" or "1" **. Double-ended queues are often used. For common edge lengths, Dijkstra's algorithm is suitable, and priority queues are often used.


If "distance" is redefined as "movement cost" and "passage movement cost is 0" and "wall movement cost is 1", "whether the wall can be moved up to twice to reach the goal" can be calculated. The amount of calculation of 01-BFS is $ O (V + E) $ when the number of vertices is $ V $ and the number of sides is $ E $, which is equivalent to normal BFS. AC with Python3, but with PyPy3 it becomes MLE (Memory Limit Exceeded).

Sample code

#Double-ended queue(double-ended queue)import
from collections import deque
s=[input()for i in range(h)]
for i in range(h):
	for j in range(w):
                #Read the starting point
		if s[i][j]=="s":
                #Read goal point
		elif s[i][j]=="g":
deq=deque([(sx,sy)])            #01 from the starting point-BFS start
dis=[[inf]*w for i in range(h)] #Initialize at infinity
d=[(1,0),(-1,0),(0,1),(0,-1)]   #Up down left right
# 01-BFS
while deq:
        #Take out the search site from the left end
	for dx,dy in d:
		if 0<=x+dx<h and 0<=y+dy<w and dis[x+dx][y+dy]==inf: #boundary condition
			if s[x+dx][y+dy]=="#":
				#Added search site on the right end
				#Added search site on the left end
print("YES" if dis[gx][gy]<=2 else "NO")

Recommended Posts

[Python] 01-BFS ARC005C
[Python] BFS (breadth-first search) ABC168D
[Python] BFS (breadth-first search) ABC007C
Algorithm in Python (breadth-first search, bfs)
kafka python
Python Summary
Built-in python
Python comprehension
Python technique
Studying python
Python 2.7 Countdown
Python FlowFishMaster
Python service
python tips
python function ①
Python basics
Python memo
ufo-> python (3)
Python comprehension
install python
Python Singleton
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Try python
Python memo
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
python underscore
Python summary
Start python
[Python] Sort
Note: Python
Python basics ③
python log
Python basics
[Scraping] Python scraping
Python update (2.6-> 2.7)
python memo
Python memorandum
Python # sort
ufo-> python
Python nslookup
python learning
Hannari Python 2020
[Rpmbuild] Python 3.7.3.
Prorate Python (1)