宝岛探险

题目描述

小哼通过秘密方法得到一张不完整的钓鱼岛航拍地图。钓鱼岛由一个主岛和一些附属岛屿组成，小哼决定去钓鱼岛探险。下面这个10∗10 的二维矩阵就是钓鱼岛的航拍地图。图中数字表示海拔，0 表示海洋，1 9 都表示陆地。小哼的飞机将会降落在(6,8) 处，现在需要计算出小哼降落所在岛的面积（即有多少个格子）。注意此处我们把与小哼降落点上下左右相链接的陆地均视为同一岛屿。

样例输入

10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

样例输出

38

```c
#include<stdio.h>
struct note{
    int x;//横坐标
    int y;//纵坐标
};

int main(){
    struct note que[2501];
    int head,tail;
    int a[51][51];
    int book[51][51] = {0};
    int i, j, k, sum, n, m, startx, starty, tx, ty;

    //定义一个方向数组
    int next[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    //读入n行m列以及小哼降落的坐标
    scanf("%d %d %d %d",&n, &m, &startx, &starty);

    //读入地图
    for (i = 1; i <= n; i ++)
        for (j = 1 ; j <= m ; j ++)
            scanf("%d",&a[i][j]);
    //队列初始化
    head = 1;
    tail = 1;
    //往队列插入起始坐标
    que[tail].x = startx;
    que[tail].y = starty;
    tail++;
    book[startx][starty] = 1;
    sum =1;

    while (head < tail){
        //枚举四个方向
        for (k = 0 ; k < 4 ; k ++){
            //计算四个方向
            tx = que[head].x + next[k][0];
            ty = que[head].y + next[k][1];
            //判断是否越界
            if (tx < 1 || tx > n || ty < 1 || ty > m) continue;

            if (a[tx][ty] > 0 && book[tx][ty] == 0){
                que[tail].x = tx;
                que[tail].y = ty;
                book[tx][ty] = 1;
                sum++;
                tail++;
            }
        }
        //当一个点扩展点结束后，head++才能继续往下扩展
        head++;
    }
    //最后输出岛屿大小
    printf("%d\n",sum);
    return 0;
}

运行结果：

dfs题解:

#include<stdio.h>
int a[51][51];
int book[51][51], n, m, sum;

void dfs(int x, int y){
    //定义一个方向数组
    int next[4][2] = {{0, 1},{1, 0},{0 ,-1},{-1, 0}};

    int k, tx, ty;

    //枚举四个方向
    for (k = 0 ; k < 4 ; k ++){
        tx = x + next[k][0];
        ty = y + next[k][1];

        //判断是否越界
        if (tx < 1 || tx > n || ty < 1 || ty > m) continue;

        //判断陆地
        if (a[tx][ty] > 0 && book[tx][ty] == 0){
            book[tx][ty] = 1;
            sum++;
            dfs(tx, ty);
        }
    }
    return ;

}

int main(){
    int i, j ,startx ,starty;
    scanf("%d %d %d %d",&n, &m, &startx, & starty);

    //读入地图
    for (i = 1 ; i <= n ; i ++)
        for (j = 1; j <=m ;j ++)
            scanf("%d",&a[i][j]);

    book[startx][starty] = 1;
    sum = 1;
    dfs(startx,starty);
    //最后输出岛屿大小
    printf("%d\n",sum);
}

运行结果：

求地图有多少个独立小岛

题解：

#include<stdio.h>
int a[51][51];
int book[51][51], n, m;
void dfs(int x, int y, int color){
    //定义一个方向数组
    int next[4][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    int k, tx, ty;
    a[x][y] = color; // 这个格子进行染色

    //枚举四个方向
    for (k = 0 ; k <= 3; k ++){
        //下一步坐标
        tx = x + next[k][0];
        ty = y + next[k][1];
        //判断是否越界
        if (tx < 1 || tx > n || ty < 1 || ty > m) continue;

        if (a[tx][ty] > 0 && book[tx][ty] == 0){
            book[tx][ty] = 1;
            dfs(tx, ty, color);
        }
    }
    return ;
}

int main(){

    int i, j , num = 0;
    scanf("%d %d", &n, &m);
    //读入地图
    for (i = 1 ; i <= n ; i ++)
        for (j = 1 ; j <= m ; j++)
            scanf("%d",&a[i][j]);



    //对每一个大于0的点尝试进行dfs染色
    for (i = 1 ; i <= n ; i ++){
        for (j = 1 ; j <= m ; j ++){
            if (a[i][j] > 0){
                num --; // 小岛需要染的颜色的编号
                //每发现一个小岛应染以不同的原色，因此每次要-1
                book[i][j] = 1;
                dfs(i, j, num);
            }
        }
    }
    //输出已经染色后的地图
    for (i = 1 ; i <= n ; i ++){
        for (j = 1 ; j <= m ; j ++){
            printf("%3d",a[i][j]);
        }printf("\n");
    }

        printf("有%d个小岛\n",-num);
}

此算法为Floodfill漫水填充法，也称种子填充法