【广度优先搜索2】迷宫最短路径问题

题解

题面描述

给定一个大小为 m × n 的二维矩阵，其中每个元素表示一个格子。矩阵中的每个格子可以是空白（用 0 表示），或者是墙（用 1 表示）。你需要找到从给定的起始点到目标点之间的最短路径长度。

你可以从当前格子向上下左右四个方向移动，且只能移动到相邻的空白格子。若无法到达目标点，请返回 -1。

思路

用 BFS 方法，第一个走到终点的状态的步数一定是最少的。

为什么 BFS 一定是最短路径？

1. 层次结构：在 BFS 的过程中，每一层代表的是从起点出发，经过相同步数的格子。当我们从起点开始遍历时，BFS 会首先探索到离起点最近的格子，也就是距离起点一步的格子，然后是两步、三步的格子。直到访问到目标点。

2. 访问过的点不重复访问：BFS 在访问一个格子后，会立即标记为已访问，因此不会重复访问同一个点，也就避免了不必要的冗余计算。

具体步骤

1. 初始化和边界条件：

   • 首先要判断起点和终点是否是墙，如果是墙，直接返回 -1。

2. BFS 搜索：

   • 创建一个队列来存储当前的坐标和已经走的步数。
   • 从起点开始，依次遍历四个方向（上、下、左、右）。
   • 对于每个相邻的格子，若该格子是空白且未被访问过，加入队列并标记为已访问。

3. 结束条件：

   • 如果 BFS 完成后还未找到目标点，说明目标点不可达，返回 -1。

代码实现

from collections import deque

# 定义方向向量，分别表示上、下、左、右四个方向
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def shortest_path(grid, m, n, x1, y1, x2, y2):
    # 检查起点和终点是否为墙
    if grid[x1][y1] == 1 or grid[x2][y2] == 1:
        return -1

    # 创建访问数组，初始化为未访问
    visited = [[False] * n for _ in range(m)]
    # 创建队列存储坐标及当前路径长度
    q = deque([((x1, y1), 0)])
    visited[x1][y1] = True

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

        # 如果当前坐标是目标点，返回路径长度
        if (x, y) == (x2, y2):
            return steps

        # 尝试向四个方向移动
        for i in range(4):
            new_x, new_y = x + dx[i], y + dy[i]

            # 检查新坐标是否在范围内，且是空白格子，且未被访问
            if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 0 and not visited[new_x][new_y]:
                q.append(((new_x, new_y), steps + 1))
                visited[new_x][new_y] = True  # 标记为已访问

    # 如果队列为空仍未找到目标点，返回 -1
    return -1

def main():
    # 输入迷宫的行数和列数
    m, n = map(int, input().split())

    # 读取矩阵
    grid = []
    for i in range(m):
        row = list(map(int, input().split()))
        grid.append(row)

    # 输入起点和终点的坐标
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())

    # 调用 shortest_path 函数计算最短路径
    result = shortest_path(grid, m, n, x1, y1, x2, y2)

    # 输出结果
    print(result)

if __name__ == "__main__":
    main()

题目描述：

给定一个大小为 $m \times n$ 的二维矩阵，其中每个元素表示一个格子。矩阵中的每个格子可以是空白（用 '0' 表示），或者是墙（用 '1' 表示）。你需要找到从给定的起始点到目标点之间的最短路径长度。

你可以从当前格子向上下左右四个方向移动，且只能移动到相邻的空白格子。若无法到达目标点，请返回 $-1$。

输入

• 第一行输入两个整数 $m$ 和 $n$（$1 \leq m, n \leq 100$），表示矩阵的行数和列数。
• 接下来输入一个 $m \times n$ 的矩阵，其中每个元素为 '0' 或 '1'，表示空白格子或墙壁。
• 接下来输入两个整数 $x_1$ 和 $y_1$（$0 \leq x_1 < m$，$0 \leq y_1 < n$），表示起点坐标。
• 接下来输入两个整数 $x_2$ 和 $y_2$（$0 \leq x_2 < m$，$0 \leq y_2 < n$），表示目标点坐标。

输出

输出一个整数，表示从起点到目标点的最短路径长度。如果目标点不可达，输出 $-1$。

示例 1

输入：

3 3
0 0 0
1 1 0
0 0 0
0 0
2 2

输出：

4