BFS模版

 1 #include<iostream>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 #include<string.h>
 6 #define maxn 101
 7 using namespace std;
 8 typedef struct
 9 {
10     int x,y;
11 }Node;
12 Node node[maxn];
13 int n,m,cnt=0;
14 int dir[8][2]={0,1,1,0,0,-1,-1,0,1,-1,-1,1,-1,-1,1,1};
15 int vis[maxn][maxn];
16 char map[maxn][maxn];
17 int is_ok(Node s)
18 {
19    if(map[s.x][s.y]==‘*‘)
20     return 0;
21    if(vis[s.x][s.y])
22     return 0;
23    if(s.x<0||s.x>=n||s.y<0||s.y>=m)
24     return 0;
25    return 1;
26 }
27 queue<Node>q;
28 void bfs(Node st)
29 {
30    Node now,next;
31    q.push(st);
32  vis[st.x][st.y]=1;
33    while(!q.empty())
34    {
35        now=q.front();
36        for(int i=0;i<8;i++)
37        {
38            next.x=now.x+dir[i][0];
39            next.y=now.y+dir[i][1];
40            if(is_ok(next))
41            {
42                q.push(next);
43                vis[next.x][next.y]=1;
44            }
45        }
46        //printf("%d %d\n",next.x,next.y);
47        q.pop();
48    }
49 }
50 int main()
51 {
52    //freopen("in.txt","r",stdin);
53     while(scanf("%d",&n)!=EOF&&n)
54     {
55         scanf("%d",&m);
56         for(int i=0;i<n;i++)
57             scanf("%s",map[i]);
58         cnt=0;
59         memset(vis,0,sizeof(vis));
60         Node no;
61         for(int i=0;i<n;i++)
62             for(int j=0;j<m;j++)
63         {
64             if(map[i][j]==‘@‘&&!vis[i][j])
65                 {
66                     no.x=i;
67                     no.y=j;
68                     bfs(no);
69                     cnt++;
70                 }
71         }
72         printf("%d\n",cnt);
73     }
74     return 0;
75 }