如何在 python 中使用门和钥匙从这个迷宫算法中获取路径?

Question

我正在尝试学习DFS/BFS，我首先使用DFS。我认为我的代码现在解决了这个问题，但我想从开始到停止获取路径。

问题： 这是迷宫问题，我需要从起点到终点坐标，你只能在陆地上旅行'.'.这是网格的表示形式

'#' = Water
'.' = Land
'a' = Key of type 'a'
'A' = Door that opens with key 'a'
'@' = starting point
'+' = finish point. 

下面是网格的示例

['.', '.', '.', 'B']
['.', 'b', '#', '.']
['@', '#', '+', '.']

这是我到目前为止的代码

def find_shortest_path(grid):
board = []
for row in grid:
column = []
row = row.replace('r', '')
for c in row:
column.append(c)
board.append(column)
ROW = len(board)
COL = len(board[0])
start = ()
stop = ()
key_set = {}
# I can collapse this with the first loop
for row in range(ROW):
for col in range(COL):
if board[row][col] == '@':
start = (row, col)
if board[row][col] == '+':
stop = (row, col)
if board[row][col].isalpha() and board[row][col].islower():
key = board[row][col]
key_set[key] = key_set.get(key, 0) + 1
visited = [[False for _ in range(COL)] for _ in range(ROW)]
def dfs(i, j):
if i < 0 or i >= ROW 
or j < 0 or j >= COL 
or visited[i][j] 
or board[i][j] == '#':
return
if i == stop[0] and j == stop[1]:
print('end')
return
print('{}, {}'.format(i, j))
if board[i][j].isalpha() and board[i][j].islower():
key_set[board[i][j]] -= 1
if board[i][j].isalpha() and board[i][j].isupper() and key_set[board[i][j].lower()] == 0:
return
visited[i][j] = True
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
print('backtrack at {}, {}'.format(i, j))
visited[i][j] = False
i, j = start
dfs(i, j)

if __name__ == '__main__':
grid = ['...Br', '.b#.r', '@#+.r']
find_shortest_path(grid)

现在我的问题是我需要返回路径。例如，此算法的结果之一将是

[[2,0], [1,0], [1,1], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3], [2, 2]]

Answer 1

如果您向dfs添加一个参数，该参数采用您当前处理的步骤编号(递归调用dfs时必须递增 1(，并且如果您使用此步骤号(例如 0 或 -1 表示"未访问"(而不是布尔值设置visited(子(数组，您可以， 找到 end 后，按照visited数组中的编号步骤操作。

如果您必须跨过同一位置两次(例如，如果钥匙处于死胡同，您必须进去拿它，然后回来去门口(，则这不起作用。但这也不适用于您当前的代码。