迷宫：寻找从起点到终点的最短路径
Maze: Finding the shortest path from start point to end point
我目前正在学习一些 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 解决方案也将受到赞赏。
修改此处给出的post：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) ]
您的 DFS 方法 returns 该特定迷宫的最短路径，因为它恰好首先选择了正确的方向，但它不会找到其他一些迷宫的最短路径。例如，对于这个迷宫：
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))
我目前正在学习一些 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 解决方案也将受到赞赏。
修改此处给出的post：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) ]
您的 DFS 方法 returns 该特定迷宫的最短路径，因为它恰好首先选择了正确的方向，但它不会找到其他一些迷宫的最短路径。例如，对于这个迷宫：
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))