当前位置：首页 > 洛谷 > 洛谷P1443题解：BFS算法求解马的移动问题

洛谷P1443题解：BFS算法求解马的移动问题

4个月前 (08-09)

一、题目解读

洛谷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循环：通过队列逐层扩展，确保最短性。

● 边界检查：确保新位置合法，防止越界。