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

胡志明t

一、问题理解

题目要求计算马从初始位置出发，到达棋盘上每个位置的最少步数。马在国际象棋中走"日"字，有8种可能的移动方向。

二、算法选择

广度优先搜索(BFS)是解决这类最短路径问题的理想选择，因为：

1.BFS按层次遍历，**次访问到某个位置时就是最短路径

2.天然适合处理网格类问题

3.实现简单直观

实现要点‌

1.队列管理‌：使用队列存储待访问的位置

2.方向数组‌：定义马移动的8个方向

3.访问标记‌：记录每个位置是否被访问过及步数

4.边界检查‌：确保移动后仍在棋盘范围内

三、完整代码

1. #include <iostream>
   
2. #include <queue>
   
3. #include <vector>
   
4. #include <cstring>
   
5. using namespace std;
   
6. 
   
7. // 定义马移动的8个方向
   
8. const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
   
9. const int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
   
10. 
    
11. int main() {
    
12.     int n, m, x, y;
    
13.     cin >> n >> m >> x >> y;
    
14.    
    
15.     // 初始化棋盘，所有位置设为-1
    
16.     vector<vector<int>> board(n+1, vector<int>(m+1, -1));
    
17.     queue<pair<int, int>> q;
    
18.    
    
19.     // 起点设置为0步
    
20.     board[x][y] = 0;
    
21.     q.push({x, y});
    
22.    
    
23.     while (!q.empty()) {
    
24.         auto current = q.front();
    
25.         q.pop();
    
26.         int cx = current.first;
    
27.         int cy = current.second;
    
28.         
    
29.         // 尝试8个方向
    
30.         for (int i = 0; i < 8; i++) {
    
31.             int nx = cx + dx[i];
    
32.             int ny = cy + dy[i];
    
33.             
    
34.             // 检查新位置是否在棋盘内且未被访问
    
35.             if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && board[nx][ny] == -1) {
    
36.                 board[nx][ny] = board[cx][cy] + 1;
    
37.                 q.push({nx, ny});
    
38.             }
    
39.         }
    
40.     }
    
41.    
    
42.     // 输出结果
    
43.     for (int i = 1; i <= n; i++) {
    
44.         for (int j = 1; j <= m; j++) {
    
45.             cout << board[i][j] << " ";
    
46.         }
    
47.         cout << endl;
    
48.     }
    
49.    
    
50.     return 0;
    
51. }

复制代码

四、代码解析

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

1.输入处理和初始化

2.BFS主循环

3.结果输出

五、 关键点说明

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

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

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

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

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

来源：洛谷题解