GroupBlog

https://vjudge.net/contest/65959#problem/L

题目大意

就是让你输入一个地图，‘#’代表空地，用’@’代表油井，让你找这片土地上的油田的个数，油田指的是，所有能从上下，左右，两条对角线相连的@，只要能连上中间不隔”#”, 就算是一个油田。

解题思路

DFS能简单些，对每一个油井，它都有八个方向，要你去查找，看是不是油井，如果是就继续对它进行判断，如果不是就结束递归。如果已经查明它是油井，就将它标记为空地。具体看代码。

代码

# include <stdio.h>
# include <string.h> 

# define max 105
int dir[8][2] = { {1,0}, {-1,0}, {0,1}, {0,-1}, {1,-1}, {1,1}, {-1,1}, {-1,-1}};

char G[max][max];

//int num[max][max];//开始以为要用到标记数组，  结果是多余的， 只要将找到的 @ 改为 * 就行了 

struct node
{
    int x, y;
};

int n,m;
void DFS(int x, int y)
{
    if(G[x][y] !='@' || x<0 || x>=n || y<0 || y>=m )
    return;
//  num[x][y] = 1;
    G[x][y] = '*';
    for(int i = 0; i<8; i++)
    {
        DFS(x+dir[i][0], y+dir[i][1]);
    }
}

int main(void)
{
    int i,j;
    while(scanf("%d%d",&n,&m), n+m)
    {
        int t = 0;
        for(i = 0; i<n; i++)
        {
            scanf("%s",G[i]);           
        }

        for(i = 0; i < n; i++)
        {
            for(j = 0; j<m; j++)
            {
                if(G[i][j] == '@' )
                {
                    t++;
                    DFS(i,j);
                }       
            }           
        }
        printf("%d\n",t);    
    }   
    return 0;
}