迷宫:找到从起点到终点的最短路径

Question

我目前正在学习一些CS基础(一周前开始(，我偶然发现了这个挑战。迷宫是一个列表列表，'#'表示一堵墙，' '表示一条开放的路径。我应该根据连续坐标找到从左下角到右上角的最短路径(col, row).我必须在不导入任何内容的情况下创建一个函数。

例如：

maze = 
[[' ', '#', ' ', '#', ' '],
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', ' ', ' ', ' ', ' '], 
['#', ' ', '#', ' ', ' '], 
[' ', ' ', '#', '#', '#']]

首先，我得到起点坐标(0, 9)，终点坐标(4, 0)。然后我需要找到最短的路径。 预期结果将是：[(0, 9), (1, 9), (1, 8), (1, 7), (2, 7), (3, 7), (4, 7), (4, 6), (4, 5), (4, 4), (4, 3), (4, 2), (4, 1), (4, 0)]。

这是我的代码：

def grid(maze):
''' Maze Properties'''
num_rows = len(maze)
num_cols = len(maze[0])
end_pt = (num_cols - 1, 0)
start_pt = (0, num_rows - 1)
print(start_pt, end_pt)
'''Recursive Function'''
def find_shortest(maze, start_point, end_point, visited, shortest_path):
'''BASE CASE'''
if start_point == end_point:
return shortest_path

adj_points = []
'''FIND ADJACENT POINTS'''
current_row = start_point[1]
current_col = start_point[0]
#UP
if current_row > 0:
if maze[current_row - 1][current_col] == " ":
adj_points.append((current_col, current_row - 1))
#RIGHT
if current_col < (len(maze[0])-1):
if maze[current_row][current_col] == " ":
adj_points.append((current_col + 1, current_row))
#DOWN
if current_row < (len(maze) - 1):
if maze[current_row + 1][current_col] == " ":
adj_points.append((current_col, current_row + 1))
#LEFT
if current_col > 0:
if maze[current_row][current_col - 1] == " ":
adj_points.append((current_col - 1, current_row))
print(adj_points)
if all(elem in visited for elem in adj_points):
return
'''LOOP THROUGH ADJACENT PTS'''
for point in adj_points:
if point not in visited:
visited.append(point)
shortest_path.append(point)
return find_shortest(maze, point, end_point, visited, shortest_path)

path = [start_pt]
visited = [start_pt]
shortest_path = find_shortest(maze, start_pt, end_pt, visited, path)
return shortest_path

我相信问题是，如果我陷入了死胡同，它应该回溯到有选择的最后一点，我没有弄清楚该怎么做。

注意：我相信这是DFS，但BFS解决方案也将不胜感激。

Answer 1

DFS 方法返回该特定迷宫的最短路径，因为它碰巧首先选择正确的方向，但它不会为其他迷宫找到最短路径。例如，对于这个迷宫：

maze = [[' ', ' ', ' ', '#', ' '],
[' ', '#', ' ', '#', ' '],
[' ', ' ', ' ', ' ', ' ']]

请注意，您的代码在#RIGHT情况下存在错误，即缺少+ 1，因此实际上您的代码找不到上述迷宫的路径。即使纠正了这个错误，它也会找到更长的路径，首先到达网格的左上角。

为了找到最短路径，最好选择BFS，因为这样您就可以确定目标的第一次命中对应于最短路径。

以下是适用于 BFS 的代码，无需进行不必要的更改。请注意，visited在这里不是一个列表，而是一本字典，它不仅告诉您访问了一个广场，还告诉您从哪个其他广场访问它。

有了这条信息，您就可以构建路径。

另外，我选择在这里从头到尾开始搜索，因为这样您就可以按照正确的顺序重建路径(展开(。否则，您必须在返回路径之前反转路径。

def grid(maze):
''' Maze Properties'''
num_rows = len(maze)
num_cols = len(maze[0])
end_pt = (num_cols - 1, 0)
start_pt = (0, num_rows - 1)
'''BFS'''
visited = {end_pt: None}
queue = [end_pt]
while queue:
current = queue.pop(0)
if current == start_pt:
shortest_path = []
while current:
shortest_path.append(current)
current = visited[current]
return shortest_path
adj_points = []
'''FIND ADJACENT POINTS'''
current_col, current_row = current
#UP
if current_row > 0:
if maze[current_row - 1][current_col] == " ":
adj_points.append((current_col, current_row - 1))
#RIGHT
if current_col < (len(maze[0])-1):
if maze[current_row][current_col + 1] == " ": ## There was an error here!
adj_points.append((current_col + 1, current_row))
#DOWN
if current_row < (len(maze) - 1):
if maze[current_row + 1][current_col] == " ":
adj_points.append((current_col, current_row + 1))
#LEFT
if current_col > 0:
if maze[current_row][current_col - 1] == " ":
adj_points.append((current_col - 1, current_row))
'''LOOP THROUGH ADJACENT PTS'''
for point in adj_points:
if point not in visited:
visited[point] = current
queue.append(point)
maze = [[' ', '#', ' ', '#', ' '],
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', ' ', ' ', ' ', ' '], 
['#', ' ', '#', ' ', ' '], 
[' ', ' ', '#', '#', '#']]
print(grid(maze))

Answer 2

修改这里给出的帖子：https://www.techiedelight.com/find-shortest-path-in-maze/

更新：代码从C++转换为Python。逻辑还是一样。

M = 10 # Rows
N = 5 # Columns
def isSafe(grid,visited,x,y):
if grid[x][y]=='#' or visited[x][y]==True:
return False # Unsafe
return True # Safe
def isValid(x,y):
if x<M and y<N and x>=0 and y>=0:
return True # Valid
return False # Invalid
def solve(grid,visited,i,j,dest_x,dest_y,curr_dist,min_dist,shortestPath,currentPath):
if i==dest_x and j==dest_y: # if destination is found, update min_dist
if curr_dist<min_dist[0]: # If a shorter distance is found
min_dist[0] = curr_dist # Update distance
shortestPath.clear() # Update path
shortestPath.extend(currentPath)
shortestPath.append((dest_y,dest_x)) # Push the destination coordinates
return
# set (i, j) cell as visited
visited[i][j] = True
currentPath.append((j,i))
# go to bottom cell
if isValid(i + 1, j) and isSafe(grid,visited,i + 1, j):
solve(grid,visited,i + 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to right cell
if isValid(i, j + 1) and isSafe(grid,visited,i, j + 1):
solve(grid,visited,i, j + 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to top cell
if isValid(i - 1, j) and isSafe(grid,visited,i - 1, j):
solve(grid,visited,i - 1, j, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
# go to left cell
if isValid(i, j - 1) and isSafe(grid,visited,i, j - 1):
solve(grid,visited,i, j - 1, dest_x, dest_y, curr_dist + 1,min_dist,shortestPath,currentPath)
visited[i][j] = False
currentPath.pop()
if __name__ == "__main__": 
min_dist = [9e10] # Start from infinity
shortestPath = [] # It will contain the path (y,x) tuples
currentPath = [] # It will store the current path temporarily
grid = [
[' ', '#', ' ', '#', ' '],
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', '#', ' ', '#', ' '], 
[' ', ' ', ' ', ' ', ' '], 
['#', ' ', '#', ' ', ' '], 
[' ', ' ', '#', '#', '#']
]
visited = []
for i in range(M):
_list = list()
for j in range(N):
_list.append(False)
visited.append(_list)
solve(grid,visited,M-1,0,0,N-1,0,min_dist,shortestPath,currentPath)
print("Minimum distance: ",min_dist[0])
print("Path: [",end=" ")
for path in shortestPath:
print('('+str(path[0])+','+str(path[1])+')',end=' ')
print("]")

输出

Minimum distance:  13
Path: [ (0,9) (1,9) (1,8) (1,7) (2,7) (3,7) (4,7) (4,6) (4,5) (4,4) (4,3) (4,2) (4,1) (4,0) ]