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

19339201706

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

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

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

三、完整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方法处理大规模数据
  
  

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