洛谷P1443题解：BFS算法求解马的移动问题
一、题目解读
洛谷P1443题要求计算在n×m的棋盘上，马从起点(x, y)出发，到达每个位置所需的最少移动步数。题目中“马”遵循国际象棋的移动规则（即走“日”字），需输出整个棋盘各点到起点的最短步数矩阵。该问题本质是求解多源最短路径，但考虑到马的移动特性，采用广度优先搜索（BFS）算法能高效解决。
二、解题思路
核心思路为：
1. BFS算法：利用队列存储待遍历的位置，从起点开始逐层扩散，确保首次到达某点的步数即为最短。
2. 方向数组优化：预先定义马可移动的8个方向（dx, dy），避免每次计算偏移量，提升效率。
3. 标记已访问：使用board数组记录步数，初始值-1表示未访问，避免重复计算。
4. 边界检查：在扩展新位置时，需判断是否在棋盘内且未被访问，保证算法正确性。
三、解题步骤
1. 初始化：读取棋盘尺寸n×m和起点坐标(x, y)，创建board数组并初始化为-1，队列q存入起点。
2. BFS主循环：
弹出队首位置，获取其坐标和步数。
遍历8个方向，计算新坐标(nx, ny)。
若新位置合法且未访问，更新board[nx][ny]为当前步数+1，并加入队列。
3. 输出结果：遍历board数组，按格式输出每个位置的步数。
四、代码与注释
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
// 定义马移动的8个方向
const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
const int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int main() {
int n, m, x, y;
cin >> n >> m >> x >> y;
// 初始化棋盘，所有位置设为-1
vector<vector<int>> board(n+1, vector<int>(m+1, -1));
queue<pair<int, int>> q;
// 起点设置为0步
board[x][y] = 0;
q.push({x, y});
while (!q.empty()) {
auto current = q.front();
q.pop();
int cx = current.first;
int cy = current.second;
// 尝试8个方向
for (int i = 0; i < 8; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
// 检查新位置是否在棋盘内且未被访问
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && board[nx][ny] == -1) {
board[nx][ny] = board[cx][cy] + 1;
q.push({nx, ny});
}
}
}
// 输出结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
return 0;
}注释说明：
● dx/dy数组：硬编码马的8个移动方向，减少重复计算。
● board初始化为-1：标记未访问状态，避免误判。
● BFS循环：通过队列逐层扩展，确保最短性。
● 边界检查：确保新位置合法，防止越界。
五、总结
本解法通过BFS算法，结合方向数组优化，实现了对马移动最短路径的高效求解。时间复杂度为O(nm)，空间复杂度为O(nm)，适用于大多数棋盘规模。该思路同样适用于其他类似“多源最短路径”问题，体现了BFS在图形遍历中的通用性。掌握此类算法对提升算法设计与优化能力具有重要意义。
原创内容 转载请注明出处
