把可走格子看成无权图的点，从起点做一次 BFS，第一次到达终点时的步数就是最短路。
OJ: luogu
题目 ID: P1746
难度:普及-
标签:bfs最短路图论网格
日期: 2026-06-19 08:07
题意
给一个 n × n 的地图：
0表示马路，可以走；1表示店铺，不能穿过。
人在起点 (x1, y1)，目标是到终点 (x2, y2)。
每次只能向上、下、左、右走一格，花费都是 1。
要求输出最少需要走多少步。
样例地图可以这样看：
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | S | 0 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 0 | 0 | T |
其中 S 是起点，T 是终点。
思路
最直接的思路，是从起点开始 DFS，尝试所有可能路径，只要走到终点就更新最优答案。
这个版本最容易理解“最短路”的朴素含义：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int n;
char g[MAXN][MAXN];
int x1_pos, y1_pos, x2_pos, y2_pos;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool vis[MAXN][MAXN];
int ans = 1e9;
bool in_board(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n;
}
void dfs(int x, int y, int step) {
if (step >= ans) {
return;
}
if (x == x2_pos && y == y2_pos) {
ans = step;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!in_board(nx, ny)) {
continue;
}
if (g[nx][ny] == '1') {
continue;
}
if (vis[nx][ny]) {
continue;
}
vis[nx][ny] = true;
dfs(nx, ny, step + 1);
vis[nx][ny] = false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> (g[i] + 1);
}
cin >> x1_pos >> y1_pos >> x2_pos >> y2_pos;
// 小数据暴力：枚举所有不重复路径，并用当前最优答案剪枝。
vis[x1_pos][y1_pos] = true;
dfs(x1_pos, y1_pos, 0);
if (ans == (int) 1e9) {
cout << -1 << '\n';
}
else {
cout << ans << '\n';
}
return 0;
}但这样会枚举大量路径，在大地图上肯定会超时。
把地图看成无权图
我们把每个可走格子看成一个点。
如果两个可走格子上下或左右相邻，就在它们之间连一条边。由于每次移动代价都一样，边权全部都是 1。
于是题目就变成了：
无权图上的单源最短路。
为什么用 BFS
在无权图里，BFS 会按距离一层一层往外扩展：
- 先到距离为
0的点； - 再到距离为
1的点； - 再到距离为
2的点。
所以某个格子第一次被访问到时，当前步数一定就是最短路长度。
特别地，终点第一次被访问到时，就已经得到了最终答案。
正式做法
- 所有距离初始化为
-1； - 起点距离设成
0，入队； - 每次取出队首格子，向四个方向扩展；
- 只把没访问过、而且是
0的格子入队。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
char g[MAXN][MAXN];
int dista[MAXN][MAXN];
int x1_pos, y1_pos, x2_pos, y2_pos;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct Node {
int x;
int y;
};
bool in_board(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= n;
}
int bfs() {
queue<Node> q;
dista[x1_pos][y1_pos] = 0;
q.push((Node){x1_pos, y1_pos});
while (!q.empty()) {
Node u = q.front();
q.pop();
if (u.x == x2_pos && u.y == y2_pos) {
return dista[u.x][u.y];
}
for (int i = 0; i < 4; i++) {
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if (!in_board(nx, ny)) {
continue;
}
if (g[nx][ny] == '1') {
continue;
}
if (dista[nx][ny] != -1) {
continue;
}
dista[nx][ny] = dista[u.x][u.y] + 1;
q.push((Node){nx, ny});
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> (g[i] + 1);
}
cin >> x1_pos >> y1_pos >> x2_pos >> y2_pos;
memset(dista, -1, sizeof(dista));
cout << bfs() << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题是很标准的网格最短路模板题。
只要识别出“每步代价相同”，就应该把它转成无权图最短路，然后直接用 BFS。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
