以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
时间: 2023-09-17 08:06:40 浏览: 178
这道题可以用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。
以DFS为例,我们可以从入口开始,每次选择一个未走过的相邻格子前进,直到到达出口或者无路可走。如果走到了出口,就找到了一条通路。如果无路可走,就回溯到上一个格子,换一个方向继续探索。
代码如下:
```python
def dfs(maze, x, y, visited):
# 如果已经到达出口,返回True
if x == len(maze) - 1 and y == len(maze[0]) - 1:
return True
# 如果当前格子已经访问过或者是障碍物,返回False
if visited[x][y] or maze[x][y] == 1:
return False
# 标记当前格子已经访问过
visited[x][y] = True
# 往四个方向探索
if x > 0 and dfs(maze, x - 1, y, visited): # 上
return True
if x < len(maze) - 1 and dfs(maze, x + 1, y, visited): # 下
return True
if y > 0 and dfs(maze, x, y - 1, visited): # 左
return True
if y < len(maze[0]) - 1 and dfs(maze, x, y + 1, visited): # 右
return True
# 如果四个方向都走不通,回溯到上一个格子
visited[x][y] = False
return False
def find_path(maze):
visited = [[False] * len(maze[0]) for _ in range(len(maze))]
# 从入口开始搜索
return dfs(maze, 0, 0, visited)
```
这个算法的时间复杂度是$O(mn)$,空间复杂度也是$O(mn)$,其中$m$和$n$分别是迷宫的行数和列数。
阅读全文