首页 > 代码库 > 拯救OIBH总部
拯救OIBH总部
拯救OIBH总部 area
【题目描述】：
OIBH总部突然被水淹没了！现在OIBH需要你的救援……
OIBH被突来的洪水淹没了>.<还好OIBH总部有在某些重要的地方起一些围墙，用*号表示，而一个封闭的*号区域洪水是进不去的……现在给出OIBH的围墙建设图，问OIBH总部没被淹到的重要区域（由"0"表示）有多少。
【输入描述】：
第一行是两个数，x和y（x,y<=500）
第二行及以下是一个由*和0组成的x*y的图。
【输出描述】：
输出没被水淹没的OIBH总部的“0”的数量。
【样例输入】 | 【样例输出】 |
4 5 00000 00*00 0*0*0 00*00 | 1 |
5 5 ***** *0*0* **0** *0*0* ***** | 5 |
【数据范围及描述】：
搜索水题，我并不想多讲
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 8 const int maxn=505; 9 const int dx[]={1,-1,0,0};10 const int dy[]={0,0,1,-1};11 char g[maxn][maxn];12 bool vis[maxn][maxn];13 int n,m;14 15 struct node16 {17 int x,y;18 };19 20 int bfs(int x,int y)21 {22 queue<node> Q;23 node top;24 Q.push((node){x,y});25 vis[x][y]=true;26 bool flag=true;27 int cnt(1);28 while(!Q.empty())29 {30 top=Q.front();31 Q.pop();32 if(top.x==1||top.x==n||top.y==1||top.y==m) flag=false;33 for(int i=0;i<4;i++)34 {35 int xx=top.x+dx[i];36 int yy=top.y+dy[i];37 if(xx<1||xx>n||yy<1||yy>m)38 {39 flag=false;40 continue;41 }42 if(!vis[xx][yy]&&g[xx][yy]==‘0‘)43 {44 vis[xx][yy]=true;45 Q.push((node){xx,yy});46 cnt++;47 }48 }49 }50 if(flag) return cnt;51 return 0;52 }53 54 55 56 int main()57 {58 scanf("%d %d\n",&n,&m);59 for(int i=1;i<=n;i++)60 gets(g[i]+1);61 memset(vis,false,sizeof(vis));62 int ans(0);63 for(int i=1;i<=n;i++)64 for(int j=1;j<=m;j++)65 {66 if(g[i][j]==‘0‘&&!vis[i][j])67 ans+=bfs(i,j);68 }69 printf("%d",ans);70 return 0;71 }
拯救OIBH总部
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。