题目重述

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

• 平地（'.'）

• 障碍物（'#'）

• 起点（'S'）

• 终点（'E'） 求从起点到终点的最短路径步数，无法到达则输出-1。

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

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

解题步骤拆解

1. 输入处理：读取矩阵尺寸和地图数据

2. 定位起止点：扫描矩阵记录S和E的坐标

3. 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++实现（带详细注释）

#include <bits/stdC++.h>using namespace std;const int N = 1005;char grid[N][N];int dist[N][N]; // 距离矩阵int n, m;int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; // 方向数组int bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof dist);
    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            // 越界检查 || 障碍物检查 || 已访问检查
            if (nx < 0 || nx >= n || ny < 0 || ny >= m 
                || grid[nx][ny] == '#' || dist[nx][ny] != -1) 
                continue;
                
            dist[nx][ny] = dist[x][y] + 1;
            if (nx == ex && ny == ey) return dist[nx][ny];
            q.push({nx, ny});
        }
    }
    return -1;}int main() {
    cin >> n >> m;
    int sx, sy, ex, ey;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'S') sx = i, sy = j;
            if (grid[i][j] == 'E') ex = i, ey = j;
        }
    
    cout << bfs(sx, sy, ex, ey);
    return 0;}

算法优化点

1. 双向BFS：当起点和终点都已知时，可减少50%搜索范围

2. A*算法：若有启发式信息可用（如坐标距离）

3. 输入优化：使用快速IO方法处理大规模数据

常见错误排查

• 忘记初始化距离矩阵为-1

• 方向数组定义不全（缺少某个方向）

• 队列pop操作后未及时处理导致逻辑错误

• 边界条件未处理（如起点即终点的情况）

参考：竞赛学习