AcWing 1076. 迷宫问题
原题链接
简单
作者:
叶枝黎曼
,
2020-11-04 21:37:47
,
所有人可见
,
阅读 373
BFS计算最短路问题
问题难点在于存储路径
利用bfs性质,最先搜索到终点的路径为最短路径
利用pre数组可以存储该路径
每一个格点由前一项推出,用pre数组记录前一项。完成bfs后,再对pre数组从最后一个点遍历到第一个点,即可得到目标路径。结果将该路径反向输出即可
BFS带路径记录
python版本
from collections import deque
def bfs():
queue = deque()
queue.append((0,0))
vis[0][0] = True
while queue:
sam = queue.popleft()
x = sam[0]
y = sam[1]
if x == n - 1 and y == n - 1:
break
for var in ways:
n_x = x + var[0]
n_y = y + var[1]
if n_x >= 0 and n_x < n and n_y >= 0 and n_y < n and vis[n_x][n_y] == False and board[n_x][n_y] == 0:
queue.append((n_x,n_y))
vis[n_x][n_y] = True
pre[n_x][n_y] = (x,y)
ways = [(0,1),(0,-1),(1,0),(-1,0)]
n = int(input())
vis = [[False]*(n + 1) for i in range(n + 1)]
board = []
for i in range(n):
board.append([int(i) for i in input().split()])
pre = [[0]*(n + 1) for i in range(n + 1)]
bfs()
res = []
x = n - 1
y = n - 1
while x != 0 or y != 0:
res.append((x,y))
sam = pre[x][y]
x = sam[0]
y = sam[1]
res.append((0,0))
res.reverse()
for var in res:
print(var[0],var[1])