12C:未名冰场

总时间限制:: 1000ms
内存限制:: 65536kB

描述

每到冬天，未名湖就会结上冰，供溜冰爱好者玩耍。今年，当你路过未名湖时，发现只有未名湖的一部分区域结成了冰，你非常好奇，想知道一共有多少块结冰区域。假定未名湖是一个n*m的方形湖面，划分成n*m个格子，每一个格子都可能结冰或者未结冰。而一块结冰区域是指连通的结冰的格子组成的，当两个格子互相处于上下、左右或者对角相邻时，则它们是连通的。

输入

输入包含多组数组，每组数据的第一行是两个正整数n, m (1 <= n <= 100, 1 <= m <= 100)，表示湖的行和列的数量，接下来包含n行，每行m个字符，表示湖上每个位置的状态。其中, "*"表示没有结冰，“@"表示该位置已经结冰。
当n=0时，表示输入结束。

输出

每组数据输出一行，输出连通的结冰区域的数量。

样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int n, m;
 5 int a[105][105];
 6 int dirx[8] = {0,0,1,1,1,-1,-1,-1};
 7 int diry[8] = {1,-1,0,1,-1,0,1,-1};
 8 void dfs(int x, int y, int val){
 9     a[x][y] = val;
10     for(int i = 0; i < 8; i++){
11         int nx = x+dirx[i], ny = y+diry[i];
12         if(a[nx][ny]==-1)
13             dfs(nx, ny, val);
14     }
15 }
16 int main(){
17     while(1){
18         cin>>n>>m;
19         if(n==0) return 0;
20         int i, j;
21         memset(a, 0, sizeof(a));
22         for(i = 1; i <= n; i++)
23             for(j = 1; j <= m; j++){
24                 char c; cin>>c;
25                 if(c=='@') a[i][j] = -1;
26             }
27         int ans = 0;
28         for(i = 1; i <= n; i++)
29             for(j = 1; j <= m; j++){
30                 if(a[i][j] == -1){
31                     ans++;
32                     dfs(i, j, ans);
33                 }
34             }
35         cout<<ans<<endl; 
36     }
37     return 0;
38 }