1 /*BFS*/ 2 #include<stdio.h> 3 #include<string.h> 4 const int maxn=100+5,maxm=1000; 5 int m,n,vis[maxn][maxn],mat[maxn][maxn],dir[10][3]={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}; 6 char s[maxn][maxn]; 7 struct node{ 8     int xpos; 9     int ypos;10     void init(int x,int y)11     {12         xpos=x;ypos=y;13     }14 }que[maxm];15 int bfs(void);16 int main()17 {18     while(scanf("%d%d",&m,&n)==2 && m){19         for(int i=0;i<m;i++)20             scanf("%s",s[i]);21         memset(mat,0,sizeof(mat));22         for(int i=0;i<m;i++)23         for(int j=0;j<n;j++){24             if(s[i][j]==‘@‘)25                 mat[i][j]=1;26         }27         int ans=bfs();28         printf("%d\n",ans);29     }30     return 0;31 }32 int bfs(void)33 {34     int totoil=0;35     memset(vis,0,sizeof(vis));36     for(int i=0;i<m;i++)37     for(int j=0;j<n;j++){38         if(!mat[i][j])39             continue;40         if(vis[i][j])41             continue;42         int head,tail;43         que[head=tail=0].xpos=i;44         que[tail++].ypos=j;45         vis[i][j]=1;46         totoil++;47         while(head!=tail){48             node a=que[head];49             for(int i=0;i<8;i++){50                 int nx=a.xpos+dir[i][0];51                 int ny=a.ypos+dir[i][1];52                 if(nx<0 || ny<0 || nx>=m || ny>=n)53                     continue;54                 if(vis[nx][ny])55                     continue;56                 if(!mat[nx][ny])57                     continue;58                 node c;59                 c.init(nx,ny);60                 que[tail]=c;61                 tail=(tail+1)%maxm;62                 vis[nx][ny]=1;63             }64             head=(head+1)%maxm;65         }66     }67     return totoil;68 }

 1 /*DFS代码量有所减少*/ 2 #include<stdio.h> 3 #include<string.h> 4 const int maxn=100+5; 5 int m,n,vis[maxn][maxn],mat[maxn][maxn],dir[10][3]={{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1}}; 6 char s[maxn][maxn]; 7 //struct node{ 8 //    int xpos; 9 //    int ypos;10 //    void init(int x,int y)11 //    {12 //        xpos=x;ypos=y;13 //    }14 //}que[maxm];15 int dfs(int x,int y);16 int main()17 {18     while(scanf("%d%d",&m,&n)==2 && m){19         int ans=0;20         for(int i=0;i<m;i++)21             scanf("%s",s[i]);22         memset(mat,0,sizeof(mat));23         memset(vis,0,sizeof(vis));24         for(int i=0;i<m;i++)25         for(int j=0;j<n;j++)26             if(s[i][j]==‘@‘)27                 mat[i][j]=1;28         for(int i=0;i<m;i++)29         for(int j=0;j<n;j++){30             if(!mat[i][j] || vis[i][j])31                 continue;32             ans+=dfs(i,j);33         }34         printf("%d\n",ans);35     }36     return 0;37 }38 int dfs(int x,int y)39 {40       if(vis[x][y]) return vis[x][y];41       vis[x][y]=1;42       for(int i=0;i<8;i++){43           int nx=x+dir[i][0];44           int ny=y+dir[i][1];45           if(nx<0 || ny<0 || nx>=m || ny>=n)46               continue;47           if(vis[nx][ny])48               continue;49           if(!mat[nx][ny])50               continue;51            dfs(nx,ny);52       }53       return 1;54 }