迷宫问题数据结构完整代码
时间: 2024-06-30 18:01:07 浏览: 6
迷宫问题是一个经典的图搜索问题,通常使用深度优先搜索(DFS)或广度优先搜索(BFS)等算法来解决。在这里,我们可以使用邻接矩阵或邻接表来表示迷宫,其中1代表可以通过的路径,0代表墙壁。以下是使用Python和邻接矩阵的简单迷宫解决方案,以及如何使用深度优先搜索:
```python
# 定义迷宫数据结构
def create_maze_matrix(maze):
rows, cols = len(maze), len(maze)
matrix = [ * cols for _ in range(rows)]
for i, row in enumerate(maze):
for j, cell in enumerate(row):
if cell == 1:
matrix[i][j] = 1
return matrix
# 定义迷宫的邻接矩阵
maze = [
[1, 1, 0, 1],
[1, 0, 1, 1],
[0, 1, 0, 1],
[1, 1, 1, 1]
]
maze_matrix = create_maze_matrix(maze)
# 使用深度优先搜索找解
visited = set()
def dfs(maze, start, end):
stack = [start]
while stack:
curr = stack.pop()
if curr == end:
return True
if curr not in visited:
visited.add(curr)
for neighbor in [(curr, curr+1), (curr, curr-1), (curr+1, curr), (curr-1, curr)]:
if 0 <= neighbor < len(maze) and 0 <= neighbor < len(maze) and maze[neighbor][neighbor] == 1:
stack.append(neighbor)
return False
# 示例:寻找起点(0, 0)到终点(3, 3)的路径
solution = dfs(maze_matrix, (0, 0), (3, 3))
if solution:
print("找到路径")
else:
print("找不到路径")
# 相关问题--
1. 邻接矩阵是如何表示迷宫的?
2. 在这个代码中,深度优先搜索是如何工作的?
3. 如何扩展这个代码来支持更复杂的迷宫搜索策略,如A*搜索?
```