python 迷宫问题深度优先
时间: 2023-11-11 13:00:45 浏览: 39
好的,针对你的问题,我可以给出以下思路:
1. 将迷宫转化为图,每个格子为一个节点,相邻的格子之间有边相连。
2. 从起点开始进行深度优先搜索,每次选择一个未访问过的相邻节点进行探索。
3. 如果探索到终点,则返回路径;否则回溯到上一个节点,继续探索其他相邻节点。
下面是 Python 代码实现:
```python
def dfs(maze, start, end):
# 将迷宫转化为图
graph = {}
for i in range(len(maze)):
for j in range(len(maze[0])):
if maze[i][j] == 0:
node = (i, j)
neighbors = []
if i > 0 and maze[i-1][j] == 0:
neighbors.append((i-1, j))
if i < len(maze)-1 and maze[i+1][j] == 0:
neighbors.append((i+1, j))
if j > 0 and maze[i][j-1] == 0:
neighbors.append((i, j-1))
if j < len(maze[0])-1 and maze[i][j+1] == 0:
neighbors.append((i, j+1))
graph[node] = neighbors
# 深度优先搜索
visited = set()
path = []
def dfs_helper(node):
visited.add(node)
path.append(node)
if node == end:
return True
for neighbor in graph[node]:
if neighbor not in visited:
if dfs_helper(neighbor):
return True
path.pop()
return False
dfs_helper(start)
return path if path[-1] == end else None
```