首页 > 代码库 > HDU 2267 How Many People Can Survive(广搜,简单)
HDU 2267 How Many People Can Survive(广搜,简单)
题目
//一道简单的广搜水题#include<queue>#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>using namespace std;struct tt{ int x,y;};char mp[310][310];int vis[310][310];//看了题解,发现只有4个方向,而不是8个方向。。。。题目貌似都没说清楚//int xx[8]={0,0,1,1,1,-1,-1,-1};//int yy[8]={1,-1,0,1,-1,0,1,-1};int xx[4]={0,0,1,-1};int yy[4]={1,-1,0,0};int one,two;int n,m;void bfs(int x,int y){ one=0,two=0; queue<tt>q; tt front,next,tmp; front.x=x,front.y=y; while(!q.empty()) q.pop(); q.push(front); vis[x][y]=1; if(mp[x][y]==‘o‘){one++;} else if(mp[x][y]==‘v‘){two++;} while(!q.empty()) { tmp=q.front(); q.pop(); for(int i=0;i<4;i++) { next.x=tmp.x+xx[i]; next.y=tmp.y+yy[i]; if(next.x<0||next.x>=n||next.y<0||next.y>=m) { one=0,two=0;return; } else if(mp[next.x][next.y]!=‘#‘&&vis[next.x][next.y]==0) { vis[next.x][next.y]=1; if(mp[next.x][next.y]==‘o‘){one++;} else if(mp[next.x][next.y]==‘v‘){two++;} q.push(next); } } }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) scanf("%s",mp[i]); int ansone=0,anstwo=0; for(int i=1;i<n-1;i++) { for(int j=1;j<m-1;j++) { if(vis[i][j]==0&&mp[i][j]!=‘#‘) { bfs(i,j); if(one==two)one=two=0; else if(one>two)two=0; else if(two>one)one=0; ansone+=one; anstwo+=two; } } } printf("%d %d\n",ansone,anstwo); } return 0;}
HDU 2267 How Many People Can Survive(广搜,简单)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。