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]
q=Queue()
row=0
column=0
q.put(row,column)
while not q.empty():
     row,col=q.get()
     if matrix[row][col+1]=="0" and col+1<len(matrix[0]):
         q.put(row,col+1)
         matrix[row][col+1]="2"
    if matrix[row+1][col]=="0" and row+1<len(matrix):
         q.put(row+1,col)
         matrix[row+1][col]="3"
    if matrix[row][col-1]=="0" and col-1>len(matrix[0]):
         q.put(row,col-1)
         matrix[x][x-1]="4"
    if matrix[row-1][col]=="0" and row-1<len(matrix):
         q.put(row-1,col)
         matrix[row-1][col]="5"

为了获得 "Yes"（如果有路径）和 "No"（如果没有路径）的输出，我可以在末尾添加什么？

这是包含矩阵的文本文件示例。

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

我试着在最后添加这个。我运行我的代码，它说“'int' 对象不可迭代”

if matrix[7][7]=="2" "3" "4" or "5":
   print "yes"
else:
   print "no"

Answer 1

您的代码有几个问题。

首先，需要将(row, col)元组放入队列。

其次，您需要更改 `if 测试中的逻辑顺序。首先测试新的行或列索引是否在矩阵内部，然后测试该位置是否包含“0”。

一旦整个矩阵被映射，你只需要测试矩阵中的最后一个位置是否等于“0”。

这是您的代码的修复版本。

from queue import Queue

def show(matrix):
    for line in matrix:
        print(*line)
    print()

maze = '''\
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
'''

matrix = maze.splitlines()
matrix = [i.strip() for i in matrix]
matrix = [i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])

show(matrix)

# Explore the maze
q = Queue()
row = 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"

show(matrix)
row, col = numrows - 1, numcols - 1
current = matrix[row][col]
if current == "0":
    print('No path exists')
else:
    print('Success!')

输出

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

4 2 2 2 1 5 2 2
3 1 1 3 1 5 1 3
3 1 4 3 1 5 1 3
3 2 2 1 5 2 1 3
3 1 3 1 5 1 1 3
3 2 1 1 5 1 4 3
1 3 2 2 2 1 1 3
4 3 1 1 1 1 4 3

Success!

现在看看你能不能打印出迷宫的路径。
提示：从 matrix[numrows-1][numcols-1] 开始并向后工作。

顺便说一句，您应该为此任务使用 collections.deque 而不是 queue.Queue，后者通常在您的程序使用线程时使用。

Python 使用队列的广度优先搜索矩阵

Python Breadth-First Search Matrix Using Queues

python

matrix

path

breadth-first-search

maze