Submission #74301033

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int dx[]={-1,1,0,0};const int dy[]={0,0,-1,1};
int h,w;vector<vector<char>>g;vector<vector<bool>>v;
void bfs(int x,int y){
    queue<pair<int,int>>q;q.push({x,y});v[x][y]=1;
    while(!q.empty()){
        auto [cx,cy]=q.front();q.pop();
        for(int d=0;d<4;++d){
            int nx=cx+dx[d],ny=cy+dy[d];
            if(nx>=0&&nx<h&&ny>=0&&ny<w&&!v[nx][ny]&&g[nx][ny]=='.'){
                v[nx][ny]=1;q.push({nx,ny});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>h>>w;g.resize(h,vector<char>(w));v.resize(h,vector<bool>(w,0));
    for(int i=0;i<h;++i)for(int j=0;j<w;++j)cin>>g[i][j];
    for(int j=0;j<w;++j){if(g[0][j]=='.'&&!v[0][j])bfs(0,j);if(g[h-1][j]=='.'&&!v[h-1][j])bfs(h-1,j);}
    for(int i=1;i<h-1;++i){if(g[i][0]=='.'&&!v[i][0])bfs(i,0);if(g[i][w-1]=='.'&&!v[i][w-1])bfs(i,w-1);}
    int a=0;
    for(int i=1;i<h-1;++i)for(int j=1;j<w-1;++j)if(g[i][j]=='.'&&!v[i][j]){a++;bfs(i,j);}
    cout<<a<<endl;return 0;
}

Submission Info

Judge Result