C++ 第43题：std::queue 队列适配器应用：广度优先搜索模拟水波扩散路径

题目

编写程序，在一个 M × N 的二维网格地图中，给定初始注入水波的起点坐标 (sr, sc)。利用队列适配器 std::queue<std::pair<int, int>> 实现广度优先搜索（BFS），以水波逐层向上下左右四方向逐级扩散的方式计算从源点扩散到网格各单元格的最短波及步数，遇到障碍物（值为 -1）时自动绕道。

输入格式：无需外部输入（内置 5x5 网格与障碍地图）。

输出格式：整齐输出格式化打印的各网格扩散步数矩阵。

数据范围与约定：BFS 逐层拓扑推进与最短路径基石。

思路与算法

1. 先进先出 FIFO 与层级遍历
广度优先搜索的核心依托就是队列（Queue）。保证了离原点步数为 d 的所有点必然先于步数为 d + 1 的点被弹出扩展，因而天然具备求解非权图最短路径的性质。

2. 入队即打标防重
在将新坐标 push 进队列的同时，必须立刻将其标记为已访问（写入步数 dist[nr][nc] = d + 1），切忌在出队时才打标，否则同一节点会被多次重复入队导致内存与算力爆炸。

3. 方向数组技巧
使用 const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; 简洁遍历四邻域。

完整程序

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>

void bfsWaterSpread(int R, int C, int startR, int startC, const std::vector<std::vector<int>>& grid) {
    std::vector<std::vector<int>> dist(R, std::vector<int>(C, -2)); // -2: 未波及
    std::queue<std::pair<int, int>> q;

    // 标记障碍物
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (grid[r][c] == -1) dist[r][c] = -1; // 障碍
        }
    }

    // 起点入队
    dist[startR][startC] = 0;
    q.push({startR, startC});

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // 边界与障碍物检查
            if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
                if (dist[nr][nc] == -2) { // 未访问且非障碍
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc}); // 入队即打标
                }
            }
        }
    }

    std::cout << "--- 水波扩散步数矩阵 (起点在 (" << startR << "," << startC << "), # 为障碍) ---\n";
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (dist[r][c] == -1) {
                std::cout << std::setw(4) << "#";
            } else {
                std::cout << std::setw(4) << dist[r][c];
            }
        }
        std::cout << "\n";
    }
}

int main() {
    // 5x5 网格，(1,1) 和 (2,1) 为障碍物
    std::vector<std::vector<int>> grid(5, std::vector<int>(5, 0));
    grid[1][1] = -1;
    grid[2][1] = -1;
    grid[3][1] = -1;

    bfsWaterSpread(5, 5, 0, 0, grid);

    return 0;
}

运行示例

输出：

--- 水波扩散步数矩阵 (起点在 (0,0), # 为障碍) ---
   0   1   2   3   4
   1   #   3   4   5
   2   #   4   5   6
   3   #   5   6   7
   4   5   6   7   8