P1443 马的遍历
题目描述
有一个 \(n \times m\) 的棋盘，在某个点 \((x, y)\) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 \(n, m, x, y\)。
输出格式
一个 \(n \times m\) 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 \(-1\)）。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
数据规模与约定
对于全部的测试点，保证 \(1 \leq x \leq n \leq 400\)，\(1 \leq y \leq m \leq 400\)。
2022 年 8 月之后，本题去除了对输出保留场宽的要求。为了与之兼容，本题的输出以空格或者合理的场宽分割每个整数都将判作正确。
Tip
📌 题目分析
给定数据：
要求计算出马按照“日”字步规则，到达棋盘上每一个格子所需要的最少步数。如果无法到达，则输出 -1。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么求最短步数必须用 BFS？
这是搜索类题目的一条铁律： * 求所有方案数 / 连通性：用 DFS。 * 求无权图的“最短路径 / 最少步数”：必须用 BFS。
DFS 是一条路走到黑，它最先找到的路径不一定是最短的（除非你把所有路径都搜出来对比，但这绝对会超时）。 BFS 则是像水波涟漪一样，一层一层向外扩散。第一步能到的点全搜完，再去搜第二步能到的点。因此，BFS 第一次踩到某个格子的步数，绝对就是从起点到它的最短步数！
2️⃣ 马的八个方向
国际象棋中的马（和中国象棋类似）走“日”字，在一个没有任何阻挡的 5×5 区域中心，它一步可以跳到 8 个不同的位置。 我们需要用两个方向数组来记录这 8 种横纵坐标的变化规律：
3️⃣ 状态数组的妙用
题目要求不能到达的地方输出 -1。
为了极致精简代码，我们可以直接把存储答案的 dist 二维数组初始化为全部是 -1。
这样一来，这个数组同时具备了两个功能：
1. 记录答案：走到某个点时，存入所需的步数。
2. 充当 vis 访问标记：如果在 BFS 扩散时，发现下一个格子的 dist 已经不是 -1 了，说明之前已经被更短（或相等）的步数访问过，直接跳过即可。
4️⃣ 时间复杂度
在 BFS 中，借助队列，棋盘上的每个格子最多只会被入队和出队一次。
最大 \(400 \times 400 = 160000\) 个格子，计算量极小，在 1 秒时限内轻轻松松 \(0\) 毫秒秒杀。
💻 C++代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 马走“日”字的 8 个方向
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int main() {
// I/O 优化
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, x, y;
cin >> n >> m >> x >> y;
// 初始化距离数组，全部默认赋值为 -1
// 大小开到 n+1 和 m+1，方便下标从 1 开始对应坐标系
vector<vector<int>> dist(n + 1, vector<int>(m + 1, -1));
queue<pair<int, int>> q;
// 1. 起点初始化
dist[x][y] = 0;
q.push({x, y});
// 2. 广度优先搜索 BFS
while (!q.empty()) {
int cx = q.front().first;
int cy = q.front().second;
q.pop();
// 尝试向 8 个方向跳跃
for (int i = 0; i < 8; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
// 检查边界，并且必须是尚未访问过的格子（dist 为 -1）
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1) {
// 走到这一步的最短步数 = 上一步的最短步数 + 1
dist[nx][ny] = dist[cx][cy] + 1;
q.push({nx, ny});
}
}
}
// 3. 按矩阵格式输出结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << dist[i][j] << " ";
}
cout << "\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 执迷不悟使用 DFS
有些新手拿到这种棋盘走格子的题目，肌肉记忆就敲了 DFS 进去，还会特意写一个很复杂的逻辑：“如果走到某个格子的步数比以前记录的小，就更新它并继续搜”。 这是灾难级的写法！ 这会导致原本 \(O(N)\) 的图遍历退化成近乎指数级的盲目回溯，在 \(400 \times 400\) 的图里绝对会 TLE（超时）到令人发指。记住：无权最短路，只用 BFS。
❌ 2. 坐标数组对应写错
马的 8 个方向虽然很常规，但如果 dx 和 dy 没有完全匹配对应（比如写成了直走 2 步又拐 2 步），就会导致马变成了“变异马”。写完方向数组后，最好脑内过一遍：\(1^2 + 2^2 = 5\)，保证每一对坐标的变化量平方和都是 \(5\)，这才是一步纯正的“日”字。
❌ 3. 多重访问导致队列撑爆 (MLE)
入队的瞬间就要立刻改变状态/标记。
如果我们在 q.push({nx, ny}) 之后，不立刻更新 dist[nx][ny] = ...，而是等到出队 q.pop() 的时候才去更新。这会导致同一个目标格子被周边的多个邻居反复塞入队列，队列会指数级膨胀，直接触发内存超限 (MLE)。
🚀 一句话总结
🔥 补充：硬核知识点
为什么 BFS 第一次搜到就必定是最短路？
我们可以从队列的单调性来深度理解 BFS： 在 BFS 执行的过程中，队列里存储的结点的步数（距离源点的距离）总是满足一个规律：要么全都是 \(k\)，要么一部分是 \(k\)，一部分是 \(k+1\)，绝对不可能出现跨越式的值（比如同时存在步数为 \(2\) 和 \(4\) 的节点）。
这种特性被称为“两段性”和“单调性”。它保证了： 当我们从队列里拿出距离为 \(k\) 的点，去更新它的邻居时，邻居的距离必然是 \(k+1\)。而任何想要到达该邻居的其他路径，只可能在队列的更后方出现，所以后面出现的路径距离一定是 \(\ge k+1\) 的。因此，“先到先得”的原则在无权图中完美成立！