代码随想录算法训练营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;}