【题目来源】
洛谷：P1443 马的遍历 - 洛谷
【题目描述】
有一个 \(n\times m\) 的棋盘，在某个点 \((x,y)\) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
【输入】
输入只有一行四个整数，分别为 \(n,m,x,y\)。
【输出】
一个 \(n\times m\) 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 \(−1\)）。
【输入样例】
3 3 1 1
【输出样例】
0 3 2
3 -1 1
2 1 4
【解题思路】
【算法标签】
《洛谷 P1443 马的遍历》 #搜索# #广度优先搜索,BFS# #队列# #Special judge#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n, m: 棋盘的行数和列数
// x, y: 马的初始位置
// a[405][405]: 存储每个位置的最少步数
int n, m, x, y, a[405][405];// 定义位置结构体
struct node
{int x, y;
};int main()
{// 输入棋盘大小和马的初始位置cin >> n >> m >> x >> y;// 定义马移动的8个方向int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1};int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};// 初始化步数矩阵为-1（表示未访问）memset(a, -1, sizeof(a));// 创建队列用于BFSqueue<node> q;// 设置起始点步数为0，并加入队列node tp = {x, y};a[x][y] = 0;q.push(tp);// BFS遍历所有可达位置while (!q.empty()){tp = q.front();q.pop();// 尝试8个可能的移动方向for (int i = 0; i < 8; i++){int xx = tp.x + dx[i], yy = tp.y + dy[i];// 检查新位置是否合法且未被访问if (xx < 1 || xx > n || yy < 1 || yy > m || a[xx][yy] != -1){continue;}// 更新步数并加入队列a[xx][yy] = a[tp.x][tp.y] + 1;node t = {xx, yy};q.push(t);}}// 输出结果矩阵for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << a[i][j] << " ";}cout << endl;}return 0;
}
【运行结果】
3 3 1 1
0 3 2
3 -1 1
2 1 4