题目
题目描述
在某商场的地下停车场，部署了一套智能导航系统。停车场可以看作是一个 r*c 的网格矩阵，其中：0 表示该位置是空的行车道，车辆可以通行。1 表示该位置存有障碍物、立柱或其他已停放的车辆，车辆无法通行。
停车场的入口统一设在坐标 [0, 0] 处。现在有一辆车进入停车场，需要前往指定的目标车位 [m, n]。
车辆在停车场内只能沿着上、下、左、右四个方向移动，每移动一个格子计为步数 1。请你帮车主规划一条从入口到目标车位的最短路径。
输入描述 第一行输入两个整数 m 和 n，表示目标车位的行下标和列下标。 第二行输入两个整数 row 和 col，表示停车场的总行数和总列数。 接下来的 row 行，每行包含 col 个以空格分隔的整数（0 或 1），表示停车场的状态信息。
约束条件 1 < row, col < 2000 0 < m < row, 0 < n < col 入口 [0, 0] 保证为空位。
输出描述 输出一个整数，表示从入口 [0, 0] 到目标车位 [m, n] 的最短路径步数。如果由于障碍物阻挡无法到达目标位置，则输出 -1。
示例 1 输入： 1 1 3 3 0 0 0 0 0 0 0 0 0
输出： 2
说明： 停车场大小为 3x3，目标位置在 [1, 1]。 最短路径序列可为：[0, 0] -> [0, 1] -> [1, 1]，共移动 2 步。 或者：[0, 0] -> [1, 0] -> [1, 1]，共移动 2 步。
示例 2 输入： 2 2 3 3 0 1 0 1 1 0 0 0 0
输出： -1
说明： 由于入口 [0, 0] 的右边 [0, 1] 和下边 [1, 0] 均为障碍物（1），车辆被困在入口处，无法到达目标位置 [2, 2]，因此输出 -1。
示例 3 输入： 0 2 3 3 0 0 0 1 1 0 0 0 0
输出： 2
说明： 目标位置在 [0, 2]。虽然中间有障碍物，但可以沿着第一行直接向右行驶：[0, 0] -> [0, 1] -> [0, 2]，步数为 2。
思路
寻找最短路径的最佳算法是广度优先搜索 (BFS)。BFS 能够保证最先到达目标点的路径一定是最短的。
核心步骤：
- 合法性校验：首先检查起点 [0, 0] 或目标点 [m, n] 是否为障碍物（1）。如果是，直接返回 -1。
- 初始化：创建一个队列，存放当前探索到的坐标和步数 (x, y, step)。起始放入 (0, 0, 0)。
- 防重访问：创建一个 visited 矩阵（或直接修改原矩阵），记录已经走过的位置，避免死循环。
- 循环搜索：从队列中弹出队首元素。判断是否到达目标点，如果是，返回当前步数。向四个方向（上下左右）扩散，检查新坐标是否在矩阵边界内、是否是通道（0）、且未被访问。满足条件的坐标入队，并标记为已访问。
- 终点不可达：如果队列为空仍未找到目标点，则说明路径不通，返回 -1。
代码实现
Python
import sys
from collections import deque
def solve():
# 1. 读取目标位置 m (行), n (列)
line1 = sys.stdin.readline().split()
m, n = map(int, line1)
# 2. 读取停车场大小 row (总行数), col (总列数)
line2 = sys.stdin.readline().split()
row, col = (, line2)
matrix = []
_ (row):
matrix.append(((, sys.stdin.readline().split())))
matrix[m][n] == :
()
m == n == :
()
queue = deque([(, , )])
visited = [[ _ (col)] _ (row)]
visited[][] =
directions = [(-, ), (, ), (, -), (, )]
queue:
curr_r, curr_c, dist = queue.popleft()
dr, dc directions:
nr, nc = curr_r + dr, curr_c + dc
<= nr < row <= nc < col:
matrix[nr][nc] == visited[nr][nc]:
nr == m nc == n:
(dist + )
visited[nr][nc] =
queue.append((nr, nc, dist + ))
()
__name__ == :
solve()
