题解 | 挡住洪水

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1000100087;
int a,b; 
char s[510][510];
int st[510][510];

void solve(){
	cin>>a>>b;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			cin>>s[i][j];
		}
	}
	int dx[]={0,0,1,-1};
	int dy[]={1,-1,0,0};
	queue<pair<int,int>> q;
	q.push({0,0});
	st[0][0]=1;
	while(q.size()){
		int x1=q.front().first;
		int y1=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int aa=x1+dx[i];
			int bb=y1+dy[i];
			if(aa<0||bb<0||aa>a+1||bb>b+1) continue;
			if(st[aa][bb]) continue;
			if(s[aa][bb]=='*') continue;
			st[aa][bb]=1;
			q.push({aa,bb});
		}
	}
	int ans=0;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			if(!st[i][j]&&s[i][j]=='0') ans++;
		}
	}
	cout<<ans<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

这道题本质上是想找被围墙包起来的0的数量，我们可以从当前矩阵的往外一层的（0,0）处开始BFS，只要没有围墙，洪水就能进入矩阵