洛谷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;
}

四、代码解析

代码主要分为以下几个部分：

1.输入处理和初始化

2.BFS主循环

3.结果输出

五、 关键点说明

1.方向数组dx和dy定义了马的所有可能移动

2.使用二维数组board记录步数，初始值为-1表示未访问

3.队列q存储待处理的网格位置

4.每次从队列取出当前位置，尝试8个方向移动

5.对新位置进行边界检查和访问检查