** 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
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):
#Read the starting point
if s[i][j]=="s":
sx=i
sy=j
#Read goal point
elif s[i][j]=="g":
gx=i
gy=j
deq=deque([(sx,sy)]) #01 from the starting point-BFS start
dis=[[inf]*w for i in range(h)] #Initialize at infinity
dis[sx][sy]=0
d=[(1,0),(-1,0),(0,1),(0,-1)] #Up down left right
cnt=0
# 01-BFS
while deq:
#Take out the search site from the left end
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: #boundary condition
if s[x+dx][y+dy]=="#":
dis[x+dx][y+dy]=dis[x][y]+1
#Added search site on the right end
deq.append((x+dx,y+dy))
else:
dis[x+dx][y+dy]=dis[x][y]
#Added search site on the left end
deq.appendleft((x+dx,y+dy))
print("YES" if dis[gx][gy]<=2 else "NO")
Recommended Posts