迷宫问题 标准输入输出 题目描述: 迷宫求最短路径。 只能走上、下,左、右四个方向
时间: 2023-11-28 22:50:58 浏览: 38
好的,这是一个典型的迷宫问题,可以使用广度优先搜索(BFS)算法来解决。以下是 Python 的代码示例:
```python
from collections import deque
# 定义迷宫的行数和列数
n, m = map(int, input().split())
# 读入迷宫数据
maze = []
for i in range(n):
maze.append(input())
# 定义起点和终点
start_x, start_y = 0, 0
end_x, end_y = n-1, m-1
# 定义四个方向的移动量
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 定义队列和标记数组
q = deque()
visited = [[False]*m for _ in range(n)]
# 将起点加入队列,并标记为已访问
q.append((start_x, start_y, 0))
visited[start_x][start_y] = True
# BFS算法
while q:
x, y, step = q.popleft()
# 到达终点,输出步数并结束程序
if x == end_x and y == end_y:
print(step)
break
# 尝试四个方向的移动
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 判断是否越界或访问过
if nx < 0 or nx >= n or ny < 0 or ny >= m or visited[nx][ny] or maze[nx][ny] == '1':
continue
# 将新位置加入队列,并标记为已访问
q.append((nx, ny, step+1))
visited[nx][ny] = True
```
其中,首先读入迷宫的行数和列数,以及迷宫的数据。然后定义起点和终点,以及四个方向的移动量。接着,定义队列和标记数组,将起点加入队列,并标记为已访问。最后,进行 BFS 算法,不断从队列中取出当前位置,尝试四个方向的移动,并将新位置加入队列,并标记为已访问。如果到达终点,则输出步数,并结束程序。