摘要：本文以「星球车勘探」为场景，用广度优先搜索（BFS）求解网格地图中的最短路问题，给出 C++ 与 Python 双语言实现，并拆解队列、状态扩展、去重、复杂度等核心考点。适合信息学竞赛入门与算法面试复习。
在少儿编程比赛和算法面试里，「最短路」是高频考点。今天我们用一个直观的场景串起来：星球车降落到一片陌生地形，地图上 0 是可走的平地、1 是陨石坑（障碍），它要从左上角开到右下角，每次只能上下左右挪一格，最少要走几步？
这正是经典的 BFS 求无权网格最短路 问题。
一、问题定义
给定一个 N×M 的网格地图：
- 0 表示可通行；
- 1 表示障碍；
- 星球车从 (0,0) 出发，每次向上下左右移动一格；
- 求到达 (N-1, M-1) 的最少步数；若无法到达，输出 -1。
例如下面的 3×3 地图，中间一格是障碍，最短路是 4 步（绕过去）：
0 0 0
0 1 0
0 0 0
二、核心思想：队列 + 分层扩展
BFS（Breadth-First Search，广度优先搜索）像水波一样从起点一圈圈向外扩散：
用 dist 数组记录每个格子的最短路步数，初始为 -1（表示未访问），既能判重，又能顺带当 visited 用。
三、C++ 实现
#include <bits/stdc++.h>
using namespace std;
// 返回左上角到右下角的最短路步数；不可达返回 -1
int bfs(const vector<vector<int>>& g) {
int n = g.size(), m = g[0].size();
if (g[0][0] == 1) return -1; // 起点就是障碍
vector<vector<int>> dist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
q.push({0, 0});
dist[0][0] = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop(); // C++17 结构化绑定
if (x == n – 1 && y == m – 1) return dist[x][y];
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < m
&& g[nx][ny] == 0 && dist[nx][ny] == -1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
return -1;
}
四、Python 实现
from collections import deque
def bfs(g):
"""返回左上角到右下角的最短路步数；不可达返回 -1"""
n, m = len(g), len(g[0])
if g[0][0] == 1:
return -1
dist = [[-1] * m for _ in range(n)]
q = deque([(0, 0)])
dist[0][0] = 0
for x, y in q:
if x == n – 1 and y == m – 1:
return dist[x][y]
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 0 and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
return -1
五、复杂度与易错点
- 时间复杂度：每个格子最多进队一次，每次扩展 4 个方向，总体 O(N×M)。
- 空间复杂度：dist 数组与队列，也是 O(N×M)。
- 易错点 1（边界）：扩展新坐标一定要判断 0 <= nx < n 且 0 <= ny < m，否则会越界。
- 易错点 2（判重）：必须用 dist == -1 判断是否访问过，否则会在一个格子间反复横跳，死循环。
- 易错点 3（起点/终点为障碍）：特判 g[0][0] == 1 直接返回 -1；终点同理（本题终点障碍情形在循环里自然返回 -1）。
六、进阶思考
七、小结
BFS 是「求无权图最短路」的首选工具，本质就是队列 + 分层扩展 + 访问标记。把它和网格地图结合起来，就能解决一大批比赛题（迷宫、岛屿、扩散、最短逃离等）。建议动手把代码敲一遍，再试着改成「输出具体路径」版本，理解会更扎实。
如果觉得有帮助，欢迎点赞收藏，也欢迎在评论区贴出你的八方向改造版 👏
