Python广度优先搜索矩阵打印路径

Question

我有这行代码，用于测试在由矩阵表示的迷宫中是否可以找到一条路径。在确定是否存在路径后，如何在末尾打印路径。我尝试过做一个堆栈，但我不知道如何继续。

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

Answer 1

因为你是用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.")