学步园

给出n行m列的矩阵，“@”代表有石油，“*”代表没有，如果含有石油的小块相邻，那么属于同一块油田。相邻包括水平、垂直和斜对角，求油田的数量。

BFS代码

#include<stdio.h>

int m, n;
char grid[105][105];
int x[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int y[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

struct node
{
    int x, y;    
}Q[10005];

void bfs(int a, int b)
{
    int top = 0, i, j, tx, ty;
    Q[top].x = a;
    Q[top++].y = b;
    grid[a][b] = '*';
    for(i = 0; i < top; i ++)
    {
        for(j = 0; j < 8; j ++)
        {
            tx = Q[i].x + x[j];
            ty = Q[i].y + y[j];
            if(tx >= 0 && ty >= 0 && tx < m && ty < n && grid[tx][ty] == '@')
            {
                grid[tx][ty] = '*';
                Q[top].x = tx;
                Q[top++].y = ty;  
            }    
        }    
    }
}

int main(){
    int i, j, cnt;
    while(scanf("%d%d", &m, &n), m)
    {
        for(i = cnt = 0; i < m; i ++)
        {
            scanf("%s", grid[i]);    
        }    
        for(i = 0; i < m; i ++)
        {
            for(j = 0; j < n; j ++)
            {
                if(grid[i][j] == '@')
                {
                    cnt++ ;
                    bfs(i, j);    
                }       
            }    
        }
        printf("%d\n", cnt);
    }
    return 0;
}

DFS代码

#include<stdio.h>

int m, n;
char grid[105][105];
int x[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int y[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int a, int b)
{
    int i, tx, ty;
    grid[a][b] = '*';
    for(i = 0; i < 8; i ++)
    {
        tx = a + x[i];
        ty = b + y[i];    
        if(tx >= 0 && ty >= 0 && tx < m && ty < n && grid[tx][ty] == '@')
        {
            dfs(tx, ty);
        } 
    }
}

int main()
{
    int i, j, cnt;
    while(scanf("%d%d", &m, &n), m)
    {
        for(i = cnt = 0; i < m; i ++)
        {
            scanf("%s", grid[i]);    
        }    
        for(i = 0; i < m; i ++)
        {
            for(j = 0; j < n; j ++)
            {
                if(grid[i][j] == '@')
                {
                    cnt++ ;
                    dfs(i, j);    
                }       
            }    
        }
        printf("%d\n", cnt);
    }
    return 0;
}