首页 > 代码库 > poj 1562 简单 bfs
poj 1562 简单 bfs
// 简单 bfs
#include <iostream>
#include<fstream>
using namespace std;
char map[110][110];
int flag[110][110];
int qu[11000][2],qe,qs,m,n;
int add[8][2]={-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1 };
void bfs(int r,int c)
{ int i,tr,tc;
qs=qe=0; flag[r][c]=1; qe++;
qu[qs][0]=r; qu[qs][1]=c;
while(qs<qe)
{ for(i=0;i<8;i++)
{ tr=qu[qs][0]+add[i][0]; tc=qu[qs][1]+add[i][1];
if(tr<=m&&tr>=1&&tc<=n&&tc>=1&&flag[tr][tc]==0&&map[tr][tc]==‘@‘)
{ qu[qe][0]=tr; qu[qe][1]=tc;
flag[tr][tc]=1; qe++;
}
}
qs++;
}
}
int main()
{ int i,j;
while(scanf("%d%d",&m,&n),m)
{ int count=0; memset(flag,0,sizeof(flag));
memset(qu,0,sizeof(qu));
for(i=1;i<=m;i++) scanf("%s",map[i]+1);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(flag[i][j]==0&&map[i][j]==‘@‘)
{ bfs(i,j); count++; }
printf("%d\n",count);
}
return 0;
}