洛谷P11228地图探险题解（CSP-J 2024真题）

胡志明t

题目重述

给定n×m的二维矩阵表示探险地图，每个格子可能是：

• 平地（'.'）
• 障碍物（'#'）
• 起点（'S'）
• 终点（'E'） 求从起点到终点的最短路径步数，无法到达则输出-1。
  
  

核心算法：BFS广度优先搜索

选择原因：BFS是解决无权图最短路径问题的**方案，时间复杂度O(nm)完全适合题目约束条件（典型n,m≤1000）

解题步骤拆解

• 输入处理：读取矩阵尺寸和地图数据
• 定位起止点：扫描矩阵记录S和E的坐标
• BFS初始化：
  
  
  • 方向数组dir[4][2]表示上下左右移动
  • 距离矩阵dist记录步数（初始化为-1）
  • 队列q存入起点坐标
    
    
• BFS执行：
  while(!q.empty()){    auto [x,y] = q.front();    q.pop();    for(方向遍历){        int nx = x+dx, ny = y+dy;        if(越界检查 || 障碍物检查 || 已访问检查) continue;        dist[nx][ny] = dist[x][y]+1;        if(到达终点) return 结果;        q.push({nx,ny});    }}
• 结果输出：根据dist矩阵输出终点值
  
  

完整C++实现（带详细注释）

1. #include <bits/stdC++.h>
   
2. using namespACe std;
   
3. 
   
4. const int N = 1005;
   
5. char grid[N][N];
   
6. int dist[N][N]; // 距离矩阵
   
7. int n, m;
   
8. int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; // 方向数组
   
9. 
   
10. int bfs(int sx, int sy, int ex, int ey) {
    
11.     memset(dist, -1, sizeof dist);
    
12.     queue<pair<int,int>> q;
    
13.     q.push({sx, sy});
    
14.     dist[sx][sy] = 0;
    
15.    
    
16.     while (!q.empty()) {
    
17.         auto [x, y] = q.front();
    
18.         q.pop();
    
19.         
    
20.         for (int i = 0; i < 4; i++) {
    
21.             int nx = x + dx[i], ny = y + dy[i];
    
22.             // 越界检查 || 障碍物检查 || 已访问检查
    
23.             if (nx < 0 || nx >= n || ny < 0 || ny >= m
    
24.                 || grid[nx][ny] == '#' || dist[nx][ny] != -1)
    
25.                 continue;
    
26.                
    
27.             dist[nx][ny] = dist[x][y] + 1;
    
28.             if (nx == ex && ny == ey) return dist[nx][ny];
    
29.             q.push({nx, ny});
    
30.         }
    
31.     }
    
32.     return -1;
    
33. }
    
34. 
    
35. int main() {
    
36.     cin >> n >> m;
    
37.     int sx, sy, ex, ey;
    
38.    
    
39.     for (int i = 0; i < n; i++)
    
40.         for (int j = 0; j < m; j++) {
    
41.             cin >> grid[i][j];
    
42.             if (grid[i][j] == 'S') sx = i, sy = j;
    
43.             if (grid[i][j] == 'E') ex = i, ey = j;
    
44.         }
    
45.    
    
46.     cout << bfs(sx, sy, ex, ey);
    
47.     return 0;
    
48. }

复制代码

算法优化点

• 双向BFS：当起点和终点都已知时，可减少50%搜索范围
• A*算法：若有启发式信息可用（如坐标距离）
• 输入优化：使用快速IO方法处理大规模数据
  
  

常见错误排查

• 忘记初始化距离矩阵为-1
• 方向数组定义不全（缺少某个方向）
• 队列pop操作后未及时处理导致逻辑错误
• 边界条件未处理（如起点即终点的情况）
  
  

转自：洛谷P11228地图探险题解（CSP-J 2024真题）