P1443-马的遍历BFS
P1443 马的遍历(BFS)
P1443 马的遍历
题目描述
有一个 n × m 的棋盘，在某个点 ( x , y ) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 n , m , x , y 。
输出格式
一个 n × m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。
输入输出样例
输入
3 3 1 1输出
0 3 2
3 -1 1
2 1 4 说明/提示
数据规模与约定
对于全部的测试点，保证 1≤ x ≤ n ≤400，1≤ y ≤ m ≤400。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=410;
int dist[N][N]; // 存储每个格子到起点的最短步数，未访问的位置初始化为 -1
typedef pair<int,int> PII;
PII q[N*N]; // 模拟队列，用于广度优先搜索 (BFS)，存储棋盘中各个点的坐标
int dx[]= {2,2,1,1,-1,-1,-2,-2}; // 马在水平方向上的移动偏移量（8个可能的走法）
int dy[]= {1,-1,2,-2,2,-2,1,-1}; // 马在垂直方向上的移动偏移量（8个可能的走法）
int n, m; // 棋盘的行数和列数（输入的规模）
// 从点 (x, y) 开始执行广度优先搜索
void bfs(int x, int y) {
// 将所有位置的距离初始化为 -1，表示尚未访问
memset(dist, -1, sizeof(dist));
// 将起点 (x, y) 入队
q[0] = {x, y};
// 起点距离为 0
dist[x][y] = 0;
int hh = 0; // 队首指针
int tt = 0; // 队尾指针（初始时队中已有一个元素，所以 tt = 0）
// 当队列不为空时，继续取出队首元素进行扩展
while (hh <= tt) {
// 取出当前队首元素并将队首指针后移
auto t = q[hh++];
// 枚举马的八个可能走法
for (int i = 0; i < 8; i++) {
int a = t.first + dx[i]; // 新位置的行坐标
int b = t.second + dy[i]; // 新位置的列坐标
// 检查新位置是否超出棋盘边界
if (a < 1 || a > n || b < 1 || b > m)
continue;
// 如果新位置已经访问过，则跳过
if (dist[a][b] >= 0)
continue;
// 更新新位置的距离为当前距离加 1
dist[a][b] = dist[t.first][t.second] + 1;
// 将新位置加入队列中
q[++tt] = {a, b};
}
}
}
int main() {
// 定义马的起始点坐标
int x0, y0;
// 从标准输入读取棋盘的行数 n、列数 m 以及马的起始坐标 (x0, y0)
scanf("%d %d %d %d", &n, &m, &x0, &y0);
// 通过 BFS 计算从起点到棋盘上每个点的最短步数
bfs(x0, y0);
// 输出棋盘上每个位置的最短步数，如果某个点无法到达则输出 -1
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%-5d", dist[i][j]); // 以宽度为 5 的格式输出，保证矩阵对齐
printf("\n");
}
return 0;
}题目解析与解题思路
1. 题目背景
题目要求在一个 n × m 的棋盘上，给定一个马的初始位置 ( x , y )，计算出马走到棋盘上任意一个点的最少步数。如果某个点不可达，则输出 -1。这是一道典型的最短路径问题，适用于无权图的广度优先搜索（BFS）。
2. 数据规模
- 棋盘尺寸：最多 400×400，即最多 160,000 个格子。
- 马的走法：每步有最多 8 个可能的移动方向。
数据规模较大但由于每个格子仅访问一次，BFS 的时间复杂度为 O(n*m) 是完全可以接受的。
3. 算法思路
使用 BFS 搜索最短路径：
由于棋盘中每一步的代价均为 1，且每次移动都是马的合法走法，使用 BFS 能确保第一次访问到某个格子时所记录的步数即为最短步数。
初始化：
用二维数组
dist记录每个格子到起点的最短步数。初始时所有位置的值设为 -1，表示未访问。将起始点的步数设为 0，并将其入队。队列操作：
使用一个数组
q模拟队列。使用两个指针hh（队首）和tt（队尾）来管理队列。队列中存储的是每个已访问位置的坐标。扩展过程：
当队列不为空时，从队列中取出一个点，然后依次检查马的八个可能走法所到达的新位置。对于每个新位置：
- 检查是否在棋盘范围内。
- 检查该位置是否未被访问（
dist值仍为 -1）。 - 如果满足条件，则更新新位置的步数（为当前位置步数 + 1），并将该位置加入队列。
结束条件：
BFS 遍历完所有能到达的点后结束。此时，
dist数组中记录了从起点到各个格子的最短步数（或 -1 表示不可达）。输出：
最后按行列遍历棋盘，将
dist数组中的值按格式输出，保证矩阵排列整齐。
4. 代码细节
数组下标从 1 开始：
题目中棋盘行列的范围从 1 开始，所以代码中所有下标均从 1 到 n 或 m。
马的移动偏移量：
使用两个数组
dx和dy分别存储马横向和纵向的移动偏移量，确保能够枚举出所有可能的 8 种走法。队列实现：
代码中使用数组
q和两个指针hh和tt来模拟队列操作，避免使用 STL 中的队列以提高效率。格式化输出：
使用
printf("%-5d", ...)保证输出时每个数字占据固定宽度，有利于矩阵效果的展示。
5. 总结
该题目的关键在于利用 BFS 遍历整个棋盘，同时利用合理的数组下标控制和边界检查，确保每个合法位置都被正确计算最短步数。BFS 能够在无权图中保证最短路径的正确性，是解决这类问题的经典算法。代码简洁高效，适合用在类似的棋盘遍历问题中。