油田 Oil Deposits

油田

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84562#problem/L

题意：

输入一个m行n列的字符矩形，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横，竖或者对角线方向），

就说题目属于同一个八连块。

样例：

Sample Input

1 1

*

3 5

*@*@*

**@**

*@*@*

1 8

@@****@*

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

0 0

Sample Output

0

1

2

2

分析：
   用dfs遍历
从每个‘@’格子出发，递归遍历它周围的‘@’格子。每次访问一个格子都进行标记，防止重复遍历。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn=;

 char pic[maxn][maxn];

 int m,n,d[maxn][maxn];

 void dfs(int x,int y,int z)

 {

 if(x<||x>=m||y<||y>=n) return;     //格子的边界

 if(d[x][y]>||pic[x][y]!='@') return;                      //遍历过的格子和没在八连块中的格子

  d[x][y]=z;                //对遍历过的格子进行标记

    for(int r=-;r<=;r++)

        for(int c=-;c<=;c++)

            if(r!=||c!=)  dfs(x+r,y+c,z);

 }

 int main()

 {

     int i;

     while(scanf("%d%d",&m,&n)==&&m&&n)

     {

     for( i=;i<m;i++)

         cin>>pic[i];

     memset(d,,sizeof(d));

     int c=;

     for( i=;i<m;i++)

         for(int j=;j<n;j++)

             if(d[i][j]==&pic[i][j]=='@')

                 dfs(i,j,++c);

             cout<<c<<endl;

     }

 return ;

 }