利用栈的基本操作实现一个迷宫求解问题。
时间: 2024-05-05 17:16:36 浏览: 7
1. 定义一个栈,用于存储路径信息。
2. 定义一个迷宫矩阵,用于表示迷宫的地图。
3. 定义一个起点和终点。
4. 将起点入栈。
5. 进入循环,判断栈是否为空,如果为空则退出循环。
6. 取出栈顶元素作为当前位置,判断是否为终点,如果是则输出路径信息并退出循环。
7. 如果当前位置不是终点,则遍历当前位置的四周,判断是否可走。
8. 如果可以走,则将该位置入栈,并将当前位置标记为已走过。
9. 如果不可走,则将该位置标记为不可走。
10. 重复步骤5~9,直到找到终点或栈为空。
下面是一个简单的示例代码:
```python
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
start = (1, 1)
end = (8, 8)
stack = [start]
visited = set()
while stack:
x, y = stack[-1]
if (x, y) == end:
print("Path found:", stack)
break
found = False
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx, ny = x + dx, y + dy
if (nx, ny) in visited or maze[nx][ny] == 1:
continue
stack.append((nx, ny))
visited.add((nx, ny))
found = True
break
if not found:
stack.pop()
```