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

rhsgfswg

一、问题理解

题目要求计算马从初始位置出发，到达棋盘上每个位置的最少步数。马在国际象棋中走"日"字，有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.对新位置进行边界检查和访问检查

来源：洛谷题解