首页 > 代码库 > 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;}
View Code

 

HDU 2267 How Many People Can Survive(广搜,简单)