迷宫问题数据结构代码
时间: 2023-12-10 17:35:32 浏览: 38
以下是使用深度优先搜索(DFS)策略解决迷宫问题的Python代码:
```python
def dfs(maze, start, end):
stack = [start] # 使用栈来存储路径
visited = set() # 使用集合来存储已经访问过的节点
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 定义四个方向:上下左右
while stack:
node = stack.pop() # 取出栈顶元素
if node == end: # 如果找到了终点,返回路径
return True
visited.add(node) # 将当前节点标记为已访问
for direction in directions: # 遍历四个方向
x = node[0] + direction[0]
y = node[1] + direction[1]
if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0 and (x, y) not in visited:
stack.append((x, y)) # 将符合条件的节点加入栈中
return False # 如果没有找到终点,返回False
```
其中,maze是一个二维数组,0表示可以通过的地方,1表示墙壁不能通过的地方。start和end分别是起点和终点的坐标。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)