深搜练习1

2816: 勘探油田

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte 总提交: 1405 测试通过:842

描述

某石油勘探公司正在按计划勘探地下油田资源。他们工作在一片长方形的地域中，首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测每一块小正方形区域是否有油。若在一块小正方形区域中探测到有油，则标记为’@’，否则标记为’*’。如果两个相邻区域都为1，那么它们同属于一个石油带，一个石油带可能包含很多小正方形区域，而你的任务是要确定在一片长方形地域中有多少个石油带。所谓相邻，是指两个小正方形区域上下、左右、左上右下或左下右上同为’@’。

输入

每个长方形地域，输出油带的个数，每个油带值占独立的一行。油带值不会超过100。

样例输入

3 5
*@*@*
**@**
*@*@*
0 0

样例输出

1

---

思路： 在地图上先记下‘@’的坐标，遍历‘@’坐标，进行深搜，在每次深搜前，先判断坐标地图上是否为‘@’,每次深搜油带+1。深搜可以走八个方向，每次将搜到的油田为’*’

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n,m,c,a1,f,s;
char gra[105][105];   //地图
int dx[105],dy[105];  //油田的坐标
int x[]={1,-1,0,0,1,-1,-1,1};
int y[]={0,0,1,-1,1,-1,1,-1};
void dfs(int xx,int yy){

    if(gra[xx][yy]=='@')   //如果找到标记为'*'
    {
        gra[xx][yy]='*';
    }
    for(int i=0;i<8;i++)  //8个方向
    {
        int sx=xx+x[i];
        int sy=yy+y[i];
        if(sx<n && sx>=0 && sy<m && sy>=0
           && gra[sx][sy]!='*')  //在图内且能走
        {
            gra[sx][sy]='*';          //图上修改为不能走
            dfs(sx,sy);    //递归
        }
    }
}
void init()
{
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
}
int main()
{
    while(scanf("%d%d",&n,&m),n )
    {
        a1=0;s=0;
        init();
        for(int i=0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                gra[i][j]=getchar();
                if(gra[i][j]=='@')
                {
                    dx[a1]=i;
                    dy[a1++]=j;
                }
            }
        }
        for(int i=0;i<a1;i++)
        {
            if(gra[dx[i]][dy[i]]=='@')
            {
                s++;
                dfs(dx[i],dy[i]);
            }
        }
        printf("%d\n",s);
    }
    return 0;
}