洛谷P1443题：用BFS算法解决马走日问题

一、问题理解

题目要求计算马从初始位置出发，到达棋盘上每个位置的最少步数。马在国际象棋中走"日"字，有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;
}