ABC1007C There is a very easy-to-understand explanation in the problem statement. reference BFS (Breadth-first Search) Super Introduction! ~ Use the queue vividly ~
Sample code
from collections import deque
# (sx, sy)From(gx, gy)Find the shortest distance to
#If you can't reach it, inf (not expected to be output)
def bfs():
#Initialize all point distances with inf
d = [[float("inf")] * m for i in range(n)]
#Vector in 4 directions of movement
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(n):
for j in range(m):
#Set start and goal in map information
if maze[i][j] == "S":
sx = i
sy = j
if maze[i][j] == "G":
gx = i
gy = j
#Queue the starting point and set the distance to that point to 0
que = deque([])
que.append((sx, sy))
d[sx][sy] = 0
#Loop until the BFS body queue is empty
while que:
#Extract the beginning of the queue
p = que.popleft()
#If the state you took out is the goal, stop searching
if p[0] == gx and p[1] == gy:
break
#Loop in 4 directions
for i in range(4):
#The point after moving(nx, ny)To
nx = p[0] + dx[i]
ny = p[1] + dy[i]
#Judgment whether it is possible to move and whether it has already been visited
# d[nx][ny] !=I have visited inf
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
#Queue if you can move, and set the distance of that point to the distance from p+Confirm with 1
que.append((nx, ny))
d[nx][ny] = d[p[0]][p[1]] + 1
return d[gx][gy]
n, m = map(int, input().split())
#Read as a list of lists
maze = [list(input()) for i in range(n)]
print(bfs())
Recommended Posts