问题描述
我有这行代码可以测试是否用矩阵表示的迷宫中找到一条路径.确定是否存在路径后,如何在最后打印路径.我已经尝试过进行堆栈操作,但是不确定如何进行操作.
I have this line of code that tests wether or not there is a path to be found in a labyrinth represented by a matrix. How do I print the path at the end after I've determined wether or not there is a path. I've tried doing a stack but I'm not sure how to proceed.
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
推荐答案
作为@程名锐帖子的一种变体,这种DFS实现也将返回其找到的第一个路径.作为一般建议,如果您不关心最佳路径,DFS通常会比BFS为您提供更好的服务.
As a variant to @程名锐's post, this implementation of a DFS will also return the first path it has found. And as a general advice, if you don't care about the path being optimal, a DFS will usually serve you better than a BFS.
请注意,由于此图不是树,因此我们还必须确保不要绕圈运行.
Note that we also have to make sure not to run in circles, since this graph is not a tree.
# for convenience
matrix = [
["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"]
]
num_rows = len(matrix)
num_cols = len(matrix[0])
# just to be a bit more flexible, could also be passed as a function argument
goal_state = (num_rows - 1, num_cols - 1)
def dfs(current_path):
# anchor
row, col = current_path[-1]
if (row, col) == goal_state:
return True
# try all directions one after the other
for direction in [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]:
new_row, new_col = direction
if (0 <= new_row < num_rows and 0 <= new_col < num_cols and # stay in matrix borders
matrix[new_row][new_col] == "0" and # don't run in walls
(new_row, new_col) not in current_path): # don't run in circles
# try new direction
current_path.append((new_row, new_col))
if dfs(current_path): # recursive call
return True
else:
current_path.pop() # backtrack
# result a list of coordinates which should be taken in order to reach the goal
result = [(0, 0)]
if dfs(result):
print("Success!")
print(result)
else:
print("Failure!")
打印:
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (6, 1), (6, 2), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7)]
具有right -> left -> down -> up
的路径首选项的DFS遇到的第一个(但肯定不是最短的)正确路径.
The first (but for sure not shortest) correct path a DFS with the pathing preferences right -> left -> down -> up
encounters.
这篇关于Python广度优先搜索矩阵打印路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!