代码收藏家技术教程 2025-02-11

蓝桥杯1216——走迷宫（python）

题目描述

输入描述

输出描述

输入输出样例

运行限制

解题思路

BFS：广度优先搜索（Breadth-First Search）

代码实现

代码一：朴素代码

代码二：列表推导式、双端队列优化

代码三：bfs函数模块化

总结

题目描述

给定一个 $N\times M$ 的网格迷宫 $G$ 。 $G$ 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。

已知迷宫的入口位置为 $\left ( x_{1}, y_{1} \right )$ 出口位置为 $\left ( x_{2}, y_{2} \right )$ 。问从入口走到出口，最少要走多少个格子。

输入描述

输入第 1 行包含两个正整数 $N,M$ ，分别表示迷宫的大小。

接下来输入一个 $N\times M$ 的矩阵。若 $G_{i,j}=1$ 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数 $x_{1},y_{1},x_{2},y_{2}$ ，表示入口的位置和出口的位置。

$1\leqslant N,M\leqslant10 ^{2}, 0\leqslant G_{i,j}\leqslant 1, 1\leqslant x_{1},x_{2}\leqslant N,1\leqslant y_{1},y_{2}\leqslant M$ 。

输出描述

输出仅一行，包含一个整数表示答案。

若无法从入口到出口，则输出 −1。

输入输出样例

输入：
5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5 
输出：
8
运行限制

最大运行时间：1s

最大运行内存: 128M

解题思路

本题要求在迷宫中找到一条从入口到出口的最短路径，也就是要在矩阵中找到一条起点到终点的最短路径，从而可知，本题应当用 BFS（广度优先搜索）求解。

（使用 BFS 求得的路径即为最短路径）

BFS：广度优先搜索（Breadth-First Search）

这里我们简单介绍一下BFS算法。

BFS 是一种用于遍历搜索树或图的算法。它从起点开始，逐层扩展节点，先访问所有相邻的节点，再依次访问这些节点的相邻节点，直到找到目标节点为止。如图所示：

图中为一棵二叉树，起始节点为A，使用BFS搜索时：从A开始，先访问与A相邻的节点B、C，再访问与B相邻的节点D和E、与C相邻的节点F、G，以此类推……

BFS搜索的过程通常使用队列实现，搜索开始时，①先将A入队列；②接着A出队列，与A相邻的B、C入队列；③B出队列，与B相邻的D、E入队列；④C出队列，与C相邻的F、G入队列……最终完成搜索。

代码实现

本题代码可分为三个部分：

第一部分：数据读入。将迷宫的行列数 M,N、地图矩阵 maze、出入口位置分别读入。

第二部分：预处理。定义用于“上下左右移动”的偏移量、创建队列queue用于配合BFS算法实现逐层搜索、创建二维列表visited，用于记录已访问过的位置，避免重复访问。

第三部分：BFS广度优先搜索。从入口位置开始逐层搜索地图矩阵maze，直到搜索到出口位置时，搜索结束，输出所用步数steps，此时steps即为最短步数。

代码一：朴素代码

# 第一部分：数据读入
N, M = map(int, input().split())  # N表示行数，M表示列数
# 循环读取迷宫地图矩阵
maze = []
for i in range(N):
    row_input = input().split()
    row = []
    for j in row_input:
        row.append(int(j))
    maze.append(row)
# 读取入口位置、出口位置
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1  # 将出入口位置与列表索引统一

#--------------------------------------------------------------------------------
# 第二部分：预处理
# 定义偏移量
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
# 创建一个列表queue，并将入口位置及出发步数1添加到列表中
queue = [(x1, y1, 0)]
# 创建一个与迷宫大小相同的矩阵，用于记录已访问过的位置
visited = []
for i in range(N):  # 初始化list_visited列表
    list_row = []
    for j in range(M):
        list_row.append(False)
    visited.append(list_row)

visited[x1][y1] = True

#--------------------------------------------------------------------------------
# 第三部分：广度优先搜索
while queue:
    x, y, steps = queue.pop(0)  # 移除queue列表中的第一个元素，并将三元组解包
    # 判断是否到达终点
    if x == x2 and y == y2:
        print(steps)
        break

    # 遍历右、下、左、上4个方向
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        # 判断新位置是否在迷宫内、是否为道路、是否已经访问过
        if 0 <= new_x < N and 0 <= new_y < M and maze[new_x][new_y] == 1 \
                and not visited[new_x][new_y]:
            queue.append((new_x, new_y, steps+1))
            visited[new_x][new_y] = True
else:
    print(-1)

这里给出了完成本题较为朴素的代码，下面可以针对上述代码进行优化，使代码更加简洁：

代码二：列表推导式、双端队列优化

from collections import deque

# 第一部分：读取数据
N, M = map(int, input().split())  # N表示行数，M表示列数
# 读取迷宫地图矩阵
maze = [list(map(int, input().split())) for i in range(N)]
# 读取入口位置、出口位置
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1  # 将出入口位置与列表索引统一

#------------------------------------------------------------------------------
# 第二部分：预处理
# 定义偏移量
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# 创建一个队列queue，并将入口位置及出发步数1添加到队列中
queue = deque([(x1, y1, 0)])
# 创建一个与迷宫大小相同的布尔矩阵，用于记录已访问过的位置
visited = [[False] * M for _ in range(N)]
visited[x1][y1] = True

#------------------------------------------------------------------------------
# 第三部分：广度优先搜索
while queue:
    x, y, steps = queue.popleft()
    # 判断是否到达终点
    if x == x2 and y == y2:
        print(steps)
        break

    # 遍历上下左右4个方向
    for dx, dy in directions:
        new_x, new_y = x + dx, y + dy
        # 判断新位置是否在迷宫内、是否为道路、是否已经访问过
        if 0 <= new_x < N and 0 <= new_y < M and maze[new_x][new_y] == 1 \
                and not visited[new_x][new_y]:
            queue.append((new_x, new_y, steps+1))
            visited[new_x][new_y] = True
else:
    print(-1)

这段代码使用了列表推导式，简化了迷宫地图矩阵读入的过程和 visited 矩阵的创建过程，同时从collections 模块中导入了 deque 类，用于创建双端队列 queue，使得搜索过程更加灵活、便捷、高效，并且降低了代码的时间复杂度：

这里将代码一中的“列表 queue ”和代码二中的“队列 queue ”做一个简单对比：

列表（list）：

在尾部添加元素：list.append(x) 的时间复杂度为 O(1)。

在尾部删除元素：list.pop() 的时间复杂度为 O(1)。

在头部添加元素：list.insert(0, x) 的时间复杂度为 O(n)，因为需要移动所有元素。

在头部删除元素：list.pop(0) 的时间复杂度为 O(n)，同样需要移动所有元素。

双端队列（deque）：

在尾部添加元素：deque.append(x) 的时间复杂度为 O(1)。

在尾部删除元素：deque.pop() 的时间复杂度为 O(1)。

在头部添加元素：deque.appendleft(x) 的时间复杂度为 O(1)。

在头部删除元素：deque.popleft() 的时间复杂度为 O(1)。

代码三：bfs函数模块化

from collections import deque

# 定义bfs用于深度优先搜索
def bfs(x1, y1, x2, y2, maze):
    row, col = len(maze), len(maze[0])

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque([(x1, y1, 0)])
    visited = [[False] * col for _ in range(row)]
    visited[x1][y1] = True

    while queue:
        x, y, steps = queue.popleft()

        if x == x2 and y == y2:
            return steps
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < row and 0 <= new_y < col and maze[new_x][new_y] == 1 \
                    and not visited[new_x][new_y]:
                queue.append((new_x, new_y, steps+1))
                visited[new_x][new_y] = True
    return -1  # 无法到达出口，返回-1

# 主程序
N, M = map(int, input().split())  
maze = [list(map(int, input().split())) for i in range(N)]
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1  

result = bfs(x1, y1, x2, y2, maze)
print(result)

在这段代码中，将预处理部分和广度优先搜索部分集成为函数bfs，与数据读取部分独立开来，提升了代码的可复用性，在后续做题过程中遇到类似问题，可仿照本次的bfs函数完成求解。