输入:输入迷宫数组。第一行数据表示一个 n*n (n<=100)的迷宫;第二行开始的n行为迷
时间: 2023-10-25 20:03:13 浏览: 68
迷宫是一个有迷路和空地组成的区域,在迷宫中有一个起点和一个终点,我们需要通过移动来找到从起点到终点的路径。
迷宫数组是一个n*n的方格矩阵,其中1表示迷路,0表示空地。我们可以使用深度优先搜索(DFS)来找到从起点到终点的路径。
首先,我们需要定义一个数组visited来记录每个方格是否已经访问过,初始时都设置为False。
然后,我们定义一个函数dfs来进行深度优先搜索。在dfs函数中,根据当前位置和目标位置的关系进行判断,如果当前位置已经是目标位置,则找到了一条路径,返回True。否则,从当前位置的四个方向开始尝试移动,判断移动后的位置是否合法且没有被访问过,如果满足条件,继续递归地调用dfs函数。如果四个方向都无法找到路径,返回False。
最后,我们从起点位置开始调用dfs函数进行搜索,如果能找到一条路径,则找到解。否则,无解。
下面是一个示例的代码实现:
```python
def findPath(maze):
n = len(maze)
visited = [[False] * n for _ in range(n)]
def dfs(x, y):
if x == n-1 and y == n-1: # 到达终点
return True
if 0 <= x < n and 0 <= y < n and maze[x][y] == 0 and not visited[x][y]: # 判断位置是否合法
visited[x][y] = True
if dfs(x+1, y) or dfs(x-1, y) or dfs(x, y+1) or dfs(x, y-1): # 递归搜索四个方向
return True
visited[x][y] = False # 如果四个方向都无法找到路径,将该位置标记为未访问过
return False
return dfs(0, 0)
# 示例用法
maze = [
[0, 1, 0],
[1, 0, 1],
[0, 0, 0]
]
if findPath(maze):
print("存在路径")
else:
print("无解")
```
这样,我们就可以利用深度优先搜索来找到迷宫中的路径。