Python 实现一个迷宫求解算法
Python3 实例我们将使用深度优先搜索（DFS）算法来解决一个简单的迷宫问题。迷宫由一个二维数组表示，其中 0 表示可通行的路径，1 表示墙壁，2 表示起点，3 表示终点。我们将从起点开始，尝试找到一条通往终点的路径。
实例
def solve_maze(maze, start, end):
rows, cols = len(maze), len(maze[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
path = []
def dfs(x, y):
if x = rows or y = cols or maze[x][y] == 1 or visited[x][y]:
return False
visited[x][y] = True
path.append((x, y))
if (x, y) == end:
return True
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if dfs(x + dx, y + dy):
return True
path.pop()
return False
if dfs(start[0], start[1]):
return path
else:
return None
# 示例迷宫
maze = [
[2, 0, 1, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 0, 1],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 3]
]
start = (0, 0)
end = (4, 4)
result = solve_maze(maze, start, end)
print(result)
rows, cols = len(maze), len(maze[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
path = []
def dfs(x, y):
if x = rows or y = cols or maze[x][y] == 1 or visited[x][y]:
return False
visited[x][y] = True
path.append((x, y))
if (x, y) == end:
return True
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if dfs(x + dx, y + dy):
return True
path.pop()
return False
if dfs(start[0], start[1]):
return path
else:
return None
# 示例迷宫
maze = [
[2, 0, 1, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 0, 1],
[1, 1, 0, 1, 1],
[0, 0, 0, 0, 3]
]
start = (0, 0)
end = (4, 4)
result = solve_maze(maze, start, end)
print(result)
代码解析：
solve_maze函数接受迷宫、起点和终点作为参数。visited是一个二维数组，用于记录哪些位置已经被访问过，避免重复访问。path是一个列表，用于存储从起点到终点的路径。dfs是一个递归函数，用于深度优先搜索。它首先检查当前位置是否越界、是否是墙壁或已经被访问过。如果满足这些条件，则返回False。- 如果当前位置是终点，则返回
True，表示找到了一条路径。 - 对于当前位置的四个方向（上、下、左、右），递归调用
dfs函数。如果找到路径，则返回True。 - 如果所有方向都尝试过但没有找到路径，则从
path中移除当前位置，并返回False。 - 最后，如果
dfs函数返回True，则返回path，否则返回None。
输出结果：
[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
这个结果表示从起点 (0, 0) 到终点 (4, 4) 的路径。
点我分享笔记