一、问题理解
题目要求计算马从初始位置出发,到达棋盘上每个位置的最少步数。马在国际象棋中走"日"字,有8种可能的移动方向。
二、算法选择
广度优先搜索(BFS)是解决这类最短路径问题的理想选择,因为:
1.BFS按层次遍历,第一次访问到某个位置时就是最短路径
2.天然适合处理网格类问题
3.实现简单直观
实现要点
1.队列管理:使用队列存储待访问的位置
2.方向数组:定义马移动的8个方向
3.访问标记:记录每个位置是否被访问过及步数
4.边界检查:确保移动后仍在棋盘范围内
三、完整代码
#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;
}
四、代码解析
代码主要分为以下几个部分:
1.输入处理和初始化
2.BFS主循环
3.结果输出
五、 关键点说明
1.方向数组dx和dy定义了马的所有可能移动
2.使用二维数组board记录步数,初始值为-1表示未访问
3.队列q存储待处理的网格位置
4.每次从队列取出当前位置,尝试8个方向移动
5.对新位置进行边界检查和访问检查
来源:洛谷题解