hdu 1241 Oil Deposits

D - Oil Deposits

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 1241

Description

GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏。

Input

输入可能有多个矩形区域（即可能有多组测试）。每个矩形区域的起始行包含m和n，表示行和列的数量，1<=n,m<=100，如果m=0表示输入的结束，接下来是n行，每行m个字符。每个字符对应一个小方格，并且要么是'*'，代表没有油，要么是'@'，表示有油。

Output

对于每一个矩形区域，输出油藏的数量。两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻（即8个方向）。

Sample Input

 

1 1

*

3 5

*@*@*

**@**

*@*@*

1 8

@@****@*

5 5 

****@

*@@*@

*@**@

@@@*@

@@**@

0 0 

 

Sample Output

0

1

2

2

#include<iostream>
#include<stdio.h>
using namespace std;
char ma[105][105];
bool vis[105][105];
int n,m;
int dx[]={0,0,1,-1,1,-1,-1,1};
int dy[]={1,-1,0,0,1,-1,1,-1};
int ans;
void dfs(int x,int y)
{
    vis[x][y]=true;
    for(int i=0;i<8;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(!vis[nx][ny]&&(nx<n&&nx>=0)&&(ny<m&&ny>=0)&&(ma[nx][ny]=='@'))
        {
            vis[nx][ny]=true;
            dfs(nx,ny);
        }

    }
    return;
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(n+m)!=0)
    {
        for(int i=0;i<105;i++)
            for(int j=0;j<105;j++)
                vis[i][j]=false;
        for(int i=0;i<n;i++)
            scanf("%s",ma[i]);
        ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(ma[i][j]=='@'&&!vis[i][j])
                {
                    dfs(i,j);
                    ans++;
                }
            }
        }
        printf("%d
",ans);
    }
}