我有这行代码，用于测试在由矩阵表示的迷宫中是否可以找到一条路径。在确定是否存在路径后，如何在末尾打印路径。我尝试过做一个堆栈，但我不知道如何继续。
from queue import Queue
maze=open(input())
matrix=maze.readlines()
matrix=[i.strip() for i in matrix]
matrix=[i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])
q=Queue()
row=0
col=0
q.put((row,col))
while not q.empty():
row, col = q.get()
if col+1 < numcols and matrix[row][col+1] == "0":
q.put((row, col+1))
matrix[row][col+1] = "2"
if row+1 < numrows and matrix[row+1][col] == "0":
q.put((row+1, col))
matrix[row+1][col] = "3"
if 0 <= col-1 and matrix[row][col-1] == "0":
q.put((row, col-1))
matrix[row][col-1] = "4"
if 0 <= row-1 and matrix[row-1][col] == "0":
q.put((row-1, col))
matrix[row-1][col] = "5"
row,col=numrows-1,numcols-1
var=matrix[row][col]
if var=="0":
print ("There is no path.")
else:
print ("There is a path.")
这是一个示例矩阵：
0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0
因为你是用BFS来寻找路径，所以最终的逼近不可能是从起点到终点的最短路径，而实际上你只能得到哪一点与起点相连的结果。
因此，要获得精确路径，可以使用 DFS 来查找路径并使用堆栈来保存访问过的点，或者使用 Dijkstra 来查找从起点到终点的最短路径。
这是一个简单的 DFS 函数，它使用递归，路径用字符 2 表示
suc = 0
def dfs(row, col):
global suc
if suc == 1:
return
matrix[row][col] = "2"
if (row, col) == (numrows - 1, numcols - 1):
print("Success")
suc = 1
if col + 1 < numcols and matrix[row][col + 1] == "0":
dfs(row, col + 1)
if row + 1 < numrows and matrix[row + 1][col] == "0":
dfs(row + 1, col)
if 0 <= col - 1 and matrix[row][col - 1] == "0":
dfs(row, col - 1)
if 0 <= row - 1 and matrix[row - 1][col] == "0":
dfs(row - 1, col)
maze = open(input())
matrix = maze.readlines()
matrix = [i.strip() for i in matrix]
matrix = [i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])
dfs(0, 0)
var = matrix[numrows - 1][numcols - 1]
for m in matrix:
print(m)
if var == "0":
print("There is no path.")
else:
print("There is a path.")
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
