代码随想录算法训练营day51：图论02：99. 岛屿数量；100. 岛屿的最大面积

99. 岛屿数量

卡码网题目链接（ACM模式）(opens new window)

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

分析：

这道题题目是 DFS，BFS，并查集，基础题目。

本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。——这个标记的过程，无所谓最短路径还是什么，所以dfs bfs都可以用

在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如何把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

深搜

涉及到查找所有结点这种，都需要给他排除已经visited过的情况，需要visit数组！

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

int move[4][2]={0,1,1,0,0,-1,-1,0};

void dfs(int i,int j,int** visited,int **box,int m,int n){
    if(box[i][j]==0){
        return;
    }
    for(int k=0;k<4;k++){
        int fi=i+move[k][0];
        int fj=j+move[k][1];
        if(fi>=0 && fi<n && fj>=0 && fj<m && box[fi][fj]==1 && visited[fi][fj]==0) {
            visited[fi][fj]=1;
            dfs(fi,fj,visited,box,m,n);
        }
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int **box=(int **)malloc(sizeof(int*)*n);
    int **visited=(int **)malloc(sizeof(int*)*n);

    for(int i=0;i<n;i++){
        box[i]=(int*)malloc(sizeof(int)*m);
        visited[i]=(int*)malloc(sizeof(int)*m);
        for(int j=0;j<m;j++){
            scanf("%d",&box[i][j]);
            visited[i][j]=0;
        } 
        
        
    }

    int ans=0;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(box[i][j]==1 && visited[i][j]==0){
                ans++;
                dfs(i,j,visited,box,m,n);
            }
        }
        
    }
    printf("%d",ans);
    return ans;

}

广搜

一开始超时了：

根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。

应当：加入队列 就代表走过，立刻标记

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

int move[4][2]={0,1,1,0,0,-1,-1,0};
int queue[50000][2];

void bfs(int i,int j,int** box,int **visited,int front,int rear,int n,int m){
    rear++;//进队第一个
    queue[rear][0]=i;
    queue[rear][1]=j;
    visited[i][j]=1;

    while(front!=rear){//队非空
        front++;
        int xi=queue[front][0];//出队第一个，把相连的进队
        int xj=queue[front][1];
        
       
        for(int k=0;k<4;k++){
            int fi=xi+move[k][0];
            int fj=xj+move[k][1];
            if(fi>=0 && fi<n && fj>=0 && fj<m && box[fi][fj]==1 && visited[fi][fj]==0){
                rear++;//相连的进队
                visited[fi][fj]=1;
                queue[rear][0]=fi;
                queue[rear][1]=fj;
            }
        }
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int **box=(int **)malloc(sizeof(int*)*n);
    int **visited=(int **)malloc(sizeof(int*)*n);

    for(int i=0;i<n;i++){
        box[i]=(int*)malloc(sizeof(int)*m);
        visited[i]=(int*)malloc(sizeof(int)*m);
        for(int j=0;j<m;j++){
            scanf("%d",&box[i][j]);
            visited[i][j]=0;
        } 
    }

    int ans=0;
    

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(box[i][j]==1 && visited[i][j]==0){
                ans++;
                bfs(i,j,box,visited,-1,-1,n,m);
            }
        }
    }

    printf("%d",ans);
    return 0;

}

100. 岛屿的最大面积

卡码网题目链接（ACM模式）(opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

分析：

遇到一个未标记且是陆地的点，开始计算面积，搜索完附近所有未标记且是陆地的点

**在递归的时候，面积计数不能成为函数传递的参数，应当用全局变量：

eg：1——2,5；2——3,4；遍历完3、4回到5时，size应该继续增加，而不是用回1\2时的size参数

**读取输入，到数组时：scanf("%d",&box[i][j]);

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h>
#include <string.h>
#include <math.h>

int move[4][2]={0,1,1,0,0,-1,-1,0};
int ansmax=0;

int size;

void dfs(int i,int j,int** visited,int **box,int m,int n){
    if(box[i][j]==0){
        return;
    }
    for(int k=0;k<4;k++){
        int fi=i+move[k][0];
        int fj=j+move[k][1];
        if(fi>=0 && fi<n && fj>=0 && fj<m && box[fi][fj]==1 && visited[fi][fj]==0) {
            visited[fi][fj]=1;
            size++;
            ansmax=fmax(ansmax,size);
            dfs(fi,fj,visited,box,m,n);
        }
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int **box=(int **)malloc(sizeof(int*)*n);
    int **visited=(int **)malloc(sizeof(int*)*n);

    for(int i=0;i<n;i++){
        box[i]=(int*)malloc(sizeof(int)*m);
        visited[i]=(int*)malloc(sizeof(int)*m);
        for(int j=0;j<m;j++){
            scanf("%d",&box[i][j]);
            visited[i][j]=0;
        } 
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(box[i][j]==1 && visited[i][j]==0){//是陆地且未被访问过
                size=1;
                visited[i][j]=1;//访问了
                dfs(i,j,visited,box,m,n);
                ansmax=fmax(ansmax,size);
            }
        }
    }
    
    printf("%d",ansmax);
    return 0;

}