题解 | 挡住洪水

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
using ll = long long;
using pairi = pair<int, int>;
using pairll = pair<ll, ll>;
//定义行x，列y，两个方向数组，用于bfs拓展搜索的移动
vector<int>dx={-1,1,0,0};
vector<int>dy={0,0,-1,1};

int main() {
    ios;
    int x,y;cin>>x>>y;
    int all0=0;
    vector<string>mp(x);//存储地图信息
    for(string &str:mp) cin>>str;    
    vector<vector<bool>>fl(x,vector<bool>(y,false));//标记地图位置是否被访问过初始全未访问
    queue<pairi>bfs;//创建一个队列用于bfs拓展搜索的持续和判断停止，记录一对数代表地图上的位置
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            if(mp[i][j]=='0'){
                //统计中'0'数
                all0++;
                //初始化bfs队列中边界为'0'（可进行拓展）的位置，并且标记边界以访问
                if((i==0||i==x-1||j==0||j==y-1)){
                    bfs.push({i,j});
                    fl[i][j]=true;
                }
            }
        }
    }
    //如果队列bfs为空，则代表所有可拓展搜索的位置都已经完成拓展,则停止循环，否则一直搜索
    while(!bfs.empty()){
        auto [ix,iy]=bfs.front();//获得队列头的位置信息
        bfs.pop();//获取以后，移除表示已经该位置拓展过
        for(int i=0;i<4;i++){
            //循环搜索上下左右(在地图范围内，未访问，且是空地'0')
            int nx=ix+dx[i];
            int ny=iy+dy[i];
            if(nx>=0&&nx<x&&ny>=0&&ny<y&&fl[nx][ny]==false&&mp[nx][ny]=='0'){
                //把满足条件的位置放入,并标记
                bfs.push({nx,ny});
                fl[nx][ny]=true;
            }
        }
    }
    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            if(fl[i][j]==true) all0--;
        }
    }
    cout<<all0;




    return 0;
}