用python帮我写一个迷宫寻路径算法,知道两点的x,y坐标 找最短路径,并用列表把最短坐标路径表示出来
时间: 2024-02-09 17:11:26 浏览: 77
好的,我可以帮你写一个迷宫寻路径算法。这里我使用BFS算法,以下是完整代码:
```python
from collections import deque
# 迷宫地图
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]
# 起点和终点坐标
start = (0, 0)
end = (4, 4)
# BFS算法
def bfs(start, end, maze):
queue = deque()
queue.append(start)
visited = set()
visited.add(start)
parent = {}
while queue:
curr = queue.popleft()
if curr == end:
break
row, col = curr
# 上下左右四个方向
for r, c in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]:
# 如果新的坐标在地图范围内,且不是墙,且没有被访问过
if 0 <= r < len(maze) and 0 <= c < len(maze[0]) and maze[r][c] == 0 and (r, c) not in visited:
queue.append((r, c))
visited.add((r, c))
parent[(r, c)] = curr
# 找到最短路径
path = []
curr = end
while curr in parent:
path.append(curr)
curr = parent[curr]
path.append(start)
path.reverse()
return path
# 执行算法
path = bfs(start, end, maze)
print(path)
```
这个算法使用BFS遍历地图,找到起点到终点的最短路径,并返回一个表示最短路径坐标的列表。你只需要将起点和终点的坐标传入函数即可。
阅读全文