网站制作成本,网页特效模板,合肥建设工程市场价格信息网,智能模板网站建设工具思路#xff1a;因为中间部分如果是没被覆盖的#xff0c;就是周围一定有****#xff0c;这说明这个点一定与边界连不上#xff0c;反过来想#xff0c;从两边向中间延申#xff08;如果是0的话#xff09;#xff0c;这样被填充的部分就是被淹没的部分
// Problem:
…思路因为中间部分如果是没被覆盖的就是周围一定有****这说明这个点一定与边界连不上反过来想从两边向中间延申如果是0的话这样被填充的部分就是被淹没的部分
// Problem:
// P1506 拯救oibh总部
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1506
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includequeue
using namespace std;
const int N1005;
char a[N][N];
bool vis[N][N];
int n,m;
int ans;
int dx[4]{0,1,0,-1},dy[4]{1,0,-1,0};void bfs(int xx,int yy){queuepairint,int q;q.push({xx,yy});vis[xx][yy]1;//这里不要忘了把这个本身也赋值1与他的兄弟题不大相同因为边界也不能要while(q.size()){auto tq.front();q.pop();for(int i0;i4;i){int xt.firstdx[i],yt.seconddy[i];if(xnx1ymy1!vis[x][y]) vis[x][y]1,q.push({x,y});}}
}int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]*) vis[i][j]1;}}for(int i1;in;i(n-1)){for(int j1;jm;j){if(!vis[i][j]) bfs(i,j);}} for(int i1;in;i){for(int j1;jm;j(m-1)){if(!vis[i][j]) bfs(i,j);//两个边界分别枚举bfs}} for(int i1;in;i){for(int j1;jm;j){if(!vis[i][j]) ans;//统计剩下的0}}coutansendl;return 0;
}
