写一个老鼠走迷宫的Python程序,老鼠走迷宫可以采用递归求解的基本题型,我们在迷宫二维阵列中使用1表示迷宫墙壁,使用0表示老鼠可以行走的路径,试求出由入口至出口的路径。提示:老鼠的走法有上,下,左,右 (up、down、left、right)四个方向,在每前进一格之后就选一个方向前进,无法前进时退回上一步位置,选择下一个可前进方向,如此在阵列中依序测试四个方向,直到走到出口为至,当迷宫无路可走时返回到出发点。算法采用堆栈,入口约定为迷宫MAZE列表中的[0][0]元素位置,见附件图片1和2,使用入栈表示保存当前位置并尝试当前位置下的新路径,出栈取回栈顶内容表示返回上一位置并尝试下一个可选位置。
时间: 2024-03-06 08:49:35 浏览: 90
好的,以下是老鼠走迷宫的Python程序:
```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]]
# 定义堆栈类
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
# 定义老鼠走迷宫函数
def solveMaze(maze):
# 定义起点和终点
start = (0, 0)
end = (len(maze)-1, len(maze[0])-1)
# 定义堆栈和访问状态
stack = Stack()
visited = [[False] * len(maze[0]) for _ in range(len(maze))]
# 将起点入栈
stack.push(start)
# 开始遍历
while not stack.isEmpty():
# 取出栈顶元素
cur = stack.pop()
x, y = cur
# 判断是否到达终点
if cur == end:
return True
# 将当前位置标记为已访问
visited[x][y] = True
# 遍历四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
# 判断新位置是否合法且未访问
if 0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]) and not visited[new_x][new_y] and maze[new_x][new_y] == 0:
# 将新位置入栈
stack.push((new_x, new_y))
# 遍历完所有路径仍未找到终点,返回 False
return False
# 调用老鼠走迷宫函数
if solveMaze(MAZE):
print("找到了迷宫出口!")
else:
print("迷宫无解!")
```
以上程序中,我们定义了一个 `Stack` 类来实现堆栈,定义了一个 `solveMaze` 函数来实现老鼠走迷宫的功能。在 `solveMaze` 函数中,我们使用堆栈来保存当前位置,并尝试当前位置下的新路径。当遍历完所有路径仍未找到终点时,返回 False。
阅读全文