{{{ #!cplusplus /* hdu 1241 经典:BFS ymc 2008/09/16 题目大意: 有n×m的地图上,@代表石油,.代表没有石油, 相邻的@表示石油属于同一个石油,求总共有多少块石油。 注意:相邻表示连个格子水平,垂直或者对角相邻。 分析与解题思路: 每次先查找一个没有匹配过的@,然后用BFS查找所有与@匹配 的其它@。 */ #include #include using namespace std; const int N=110; char map[N][N]; bool used[N][N]; int n,m; int step[8][2]={{1,0},{-1,0},{0,1},{0,-1}, {1,1},{1,-1},{-1,1},{-1,-1}}; int Init() { scanf("%d %d",&n,&m); if(n==0&&m==0) return 0; memset(map,'*',sizeof(map)); memset(used,0,sizeof(used)); for(int i=0;i q; used[x][y]=true; q.push(x); q.push(y); int x1,y1,x2,y2; while(!q.empty()) { x1=q.front();q.pop(); y1=q.front();q.pop(); for(int k=0;k<8;k++) { x2=x1+step[k][0]; y2=y1+step[k][1]; if(x2<0||x2>=n||y2<0||y2>=m) continue; if(map[x2][y2]=='*'||used[x2][y2]==true) continue; used[x2][y2]=true; q.push(x2); q.push(y2); } } } int main() { int x,y; int ans; while(Init()) { ans=0; while(Find(x,y)) { BFS(x,y); ans++; } printf("%d\n",ans); } } }}}