题解 | 没挡住洪水

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;

int n,area_cnt,fa_area_cnt;
int g[N][N];
bool vis[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

void bfs(int x,int y){
	if(g[x][y+1]==0||vis[x][y+1]==true) return;
	
	queue<pair<int,int>> q;
	q.push({x,y+1});
	area_cnt++;
	bool fa_f=false;
	
	while(!q.empty()){
		pair<int,int> pr=q.front();q.pop();
		
		int tx,ty;
		for(int i=0;i<4;i++){
			tx=pr.first+dx[i];
			ty=pr.second+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&g[tx][ty]==1&&!vis[tx][ty]){
				vis[tx][ty]=true;
				if(g[tx][ty+1]==1&&g[tx+1][ty]==1&&g[tx][ty-1]==1&&g[tx-1][ty]==1&&!fa_f){
					fa_area_cnt++;
					fa_f=true;
				}
				q.push({tx,ty});
			}
		}
	}
}

void solve(){
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(g[i][j]==0){
				bfs(i,j);
			}
		}
	}
	
	cout<<area_cnt-fa_area_cnt<<endl;
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	char x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>x;
			if(x=='#'){
				g[i][j]=1;
			}
		}
	}
	
	solve();
	
    return 0;
}