题解 | 挡住洪水

/*这是对我上一个做法的改进，在输入矩阵时直接把外层空地入队列，之后直接bfs即可，不需要再遍历外层，简化了代码*/
#include <iostream>
#include <queue>
using namespace std;
 
int main() {
    //kd记录未淹没空地数量
    int kd = 0;
    //bfs所用队列
    queue<pair<int, int>> q;
    //输入数据
    int x, y;
    cin >> x >> y;
    char mp[x][y];
    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            cin >> mp[i][j];
            if(mp[i][j] == '0'){
                kd++;//使用kd记录空地总数
                if(i == 0 || i == x - 1 || j == 0 || j == y - 1){
                    mp[i][j] = ',';
                    q.push({i, j});
                    kd--;
                }
            }
        }
    }
    //辅助数组
    int xx[4] = {-1, 1, 0, 0};
    int yy[4] = {0, 0, -1, 1};

    //bfs算法从边界开始搜索所有淹没的格子并做标记
    while(!q.empty()){
        pair<int, int> current = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int xc = current.first + xx[i];
            int yc = current.second + yy[i];
            if(xc >= 0 && xc < x && yc >= 0 && yc < y && mp[xc][yc] == '0'){
                mp[xc][yc] = ',';
                q.push({xc, yc});
                kd--;
            }
        }
    }
 
    //输出结果
    cout << kd << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")