迷宫问题求所有路径
时间: 2023-09-01 21:13:38 浏览: 54
好的,我理解了你的问题。这是一个比较常见的算法问题,可以使用深度优先搜索(DFS)来解决。以下是基本的思路和代码示例:
1. 首先,我们需要定义一个迷宫的二维数组。其中,0表示可以通行的路,1表示墙,2表示起点,3表示终点。
2. 接下来,我们需要定义一个visited数组,用于标记当前位置是否已经被访问过。
3. 然后,我们需要编写一个递归函数来进行深度优先搜索。递归函数的参数包括当前位置的坐标、当前路径、路径列表以及visited数组。
4. 在递归函数中,首先判断当前位置是否为终点,如果是,则将当前路径添加到路径列表中。
5. 然后,遍历当前位置的四个方向,如果该方向可以通行且没有被访问过,则递归搜索该方向。
6. 最后,将当前位置的visited数组标记为已访问过,并将当前位置从路径中删除,以恢复状态。
下面是Python代码示例:
```python
def find_paths(maze):
n = len(maze)
m = len(maze[0])
visited = [[False] * m for _ in range(n)]
paths = []
def dfs(x, y, path):
if maze[x][y] == 3:
paths.append(path)
return
visited[x][y] = True
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] in [0, 3] and not visited[nx][ny]:
dfs(nx, ny, path + [(nx, ny)])
visited[x][y] = False
path.pop()
for i in range(n):
for j in range(m):
if maze[i][j] == 2:
dfs(i, j, [(i, j)])
return paths
maze = [
[2, 0, 1, 1],
[0, 0, 0, 1],
[1, 1, 0, 3],
[1, 1, 0, 1],
]
paths = find_paths(maze)
print(paths)
```
输出结果为:
```
[[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3)]]
```
以上代码可以求出所有从起点到终点的路径。如果要求最短路径,则可以在搜索时记录路径的长度,并在找到一条新路径时比较长度大小即可。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)