题解 | 挡住洪水

#include <iostream>
#include <queue>
using namespace std;

int main() {
    //kd记录空地总数
    int kd = 0;
    //ym记录被淹没的空地数量
    int ym = 0;
    //输入数据
    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记录空地总数
            }
        }
    }
    //辅助数组
    int xx[4] = {-1, 1, 0, 0};
    int yy[4] = {0, 0, -1, 1};
    int xxx[2] = {0, x - 1};
    int yyy[2] = {0, y - 1};
    //bfs算法从边界开始搜索所有淹没的格子并做标记
    queue<pair<int, int>> q;
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < y; j++){
            int now_x = xxx[i];
            int now_y = j;
            pair<int, int> now = {now_x, now_y};
            if(mp[now_x][now_y] == '0'){
                mp[now_x][now_y] = ',';
                q.push(now);
                ym++;
                while(!q.empty()){
                   pair<int, int> current = q.front();
                   q.pop();
                   for(int ii = 0; ii < 4; ii++){
                    int c_x = current.first + xx[ii];
                    int c_y = current.second + yy[ii];
                    if(c_x >=0 && c_x < x && c_y >= 0 && c_y < y && mp[c_x][c_y] == '0'){
                        mp[c_x][c_y] = ',';
                        q.push({c_x, c_y});
                        ym++;
                    }
                   }
                }
            }

        }
    }
    for(int i = 1; i < x - 1; i++){
        for(int j = 0; j < 2; j++){
            int now_x = i;
            int now_y = yyy[j];
            pair<int, int> now = {now_x, now_y};
            if(mp[now_x][now_y] == '0'){
                mp[now_x][now_y] = ',';
                q.push(now);
                ym++;
                while(!q.empty()){
                   pair<int, int> current = q.front();
                   q.pop();
                   for(int ii = 0; ii < 4; ii++){
                    int c_x = current.first + xx[ii];
                    int c_y = current.second + yy[ii];
                    if(c_x >=0 && c_x < x && c_y >= 0 && c_y < y && mp[c_x][c_y] == '0'){
                        mp[c_x][c_y] = ',';
                        q.push({c_x, c_y});
                        ym++;
                    }
                   }
                }
            }

        }
    }
    //计算并输出结果
    int res = kd - ym;
    cout << res << endl;
    return 0; 
}
// 64 位输出请用 printf("%lld")