首页 > 代码库 > 1562 poj bfs
1562 poj bfs
#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
int used[105][105];
int a[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
char s[105][105];
int n,m;
struct node
{ int x,y;};
void bfs(node k)
{ node t1,t2;
queue<node>p;
memset(used,0,sizeof(used));
p.push(k);
used[k.x][k.y]=1;
s[k.x][k.y]=‘*‘;
while(!p.empty())
{ t1=p.front();
p.pop();
for(int i=0;i<8;i++)
{ t2.x=t1.x+a[i][0]; t2.y=t1.y+a[i][1];
if(t2.x>=0&&t2.x<n&&t2.y>=0&&t2.y<m&&s[t2.x][t2.y]==‘@‘&&0==used[t2.x][t2.y])
{ p.push(t2);
used[t2.x][t2.y]=1;
s[t2.x][t2.y]=‘*‘;
}
}
}
}
int main()
{ int i,j,sum;
node k;
while(cin>>n>>m)
{ if(n==0&&m==0) break;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>s[i][j];
sum=0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(s[i][j]==‘@‘)
{ sum++;
k.x=i; k.y=j;
bfs(k);
}
cout<<sum<<endl;
}
return 0;
}