代码随想录算法训练营day52：图03：101. 孤岛的总面积；102. 沉没孤岛；103. 水流问题

101. 孤岛的总面积

卡码网：101. 孤岛的总面积(opens new window)

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

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

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

我的算法dfs：

在dfs的基础上，分别计算每次孤岛的面积，计入thissize，计算完后加到total上

每次遇到一个陆地且未访问过：进行dfs访问

        核心：一旦遇到一个陆地接触到了边界——那么thissize将始终归为0

        即使thissize归为0，也需要计算把相接处的陆地visit掉

        所以，采用了在dfs函数开头分类讨论：

                遇到边界了——size为0

                本情况非孤岛，size已经为0了——永远为0

                初始情况，size记为-1，且初始情况 不涉及到边界——size=1
                        否则初始情况标记为0，会和非孤岛 size已经为0混淆

                其他情况下size++

注意：初始情况，是怎么被启动的！！

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h>
#include <string.h>int move[4][2]={1,0,0,1,-1,0,0,-1};
int this_size;void dfs(int i,int j,int **box,int**visit,int m,int n){if(i<=0 || i>=n-1 || j<=0 || j>=m-1 || this_size==0){this_size=0;}else if(this_size==-1) this_size=1;else this_size++;for(int k=0;k<4;k++){int move_i = i+move[k][0];int move_j = j+move[k][1];if(move_i >=0 && move_i<n && move_j>=0 && move_j<m && box[move_i][move_j]==1 && visit[move_i][move_j]==0){visit[move_i][move_j]=1;//printf("in:%d %d size=%d\n",move_i,move_j,this_size);dfs(move_i,move_j,box,visit,m,n);}}
}int main(){int n,m;scanf("%d%d",&n,&m);int** box=(int**)malloc(sizeof(int*)*n);int **visit=(int**)malloc(sizeof(int*)*n);for (int i=0;i<n;i++){box[i]=(int*)malloc(sizeof(int)*m);visit[i]=(int*)malloc(sizeof(int)*m);for(int j=0;j<m;j++){scanf("%d",&box[i][j]);visit[i][j]=0;}}int total_area=0;for (int i=0;i<n;i++){for(int j=0;j<m;j++){if(box[i][j]==1 && visit[i][j]==0){this_size=-1;visit[i][j]=1;dfs(i,j,box,visit,m,n);total_area=total_area+this_size;}}}printf("%d",total_area);return 0;
}

改成bfs：

int front=-1;
int rear=-1;
int queue[10000][2];bool judge(int i,int j,int n,int m){if(i<= 0 || i>=n-1 || j<=0 || j>=m-1) return true;else return false;
}void bfs(int i,int j,int**box,int**visit,int m,int n){rear++;queue[rear][0]=i;queue[rear][1]=j;visit[i][j]=1;if(judge(i,j,n,m)) this_size=0;else this_size=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 && visit[fi][fj]==0){if(judge(fi,fj,n,m) || this_size==0) this_size=0;else this_size++;rear++;queue[rear][0]=fi;queue[rear][1]=fj;visit[fi][fj]=1;}}}
}

或者

也可以考虑：

本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

如图，在遍历地图周围四个边，靠地图四边的陆地，都为绿色，

在遇到地图周边陆地的时候，将1都变为0，此时地图为这样：

102. 沉没孤岛

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

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述：

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

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。

分析：

思路依然是从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。

有的录友可能想，我在定义一个 visited 二维数组，单独标记周边的陆地，然后遍历地图的时候同时对 数组board 和 数组visited 进行判断，决定 陆地是否变成水域。

这样做其实就有点麻烦了，不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。

步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）

步骤二：将水域中间 1 （陆地）全部改成 水域（0）

步骤三：将之前标记的 2 改为 1 （陆地）

如图：

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h>
#include <string.h>int move[4][2]={1,0,0,1,-1,0,0,-1};void dfs(int i,int j,int**box,int **visit,int m,int n){visit[i][j]=1;box[i][j]=2;for(int k=0;k<4;k++){int movei=i+move[k][0];int movej=j+move[k][1];if(movei>=0 && movej>=0 && movei<n && movej<m && visit[movei][movej]==0 && box[movei][movej]==1){dfs(movei,movej,box,visit,m,n);}}
}int main(){int n,m;scanf("%d%d",&n,&m);int** box=(int**)malloc(sizeof(int*)*n);int **visit=(int**)malloc(sizeof(int*)*n);for (int i=0;i<n;i++){box[i]=(int*)malloc(sizeof(int)*m);visit[i]=(int*)malloc(sizeof(int)*m);for(int j=0;j<m;j++){scanf("%d",&box[i][j]);visit[i][j]=0;}}for (int i=0;i<n;i++){if(box[i][0]==1 && visit[i][0]==0){dfs(i,0,box,visit,m,n);}if(box[i][m-1]==1 && visit[i][m-1]==0){dfs(i,m-1,box,visit,m,n);}}for (int i=0;i<n;i++){if(box[0][i]==1 && visit[0][i]==0){dfs(0,i,box,visit,m,n);}if(box[n-1][i]==1 && visit[n-1][i]==0){dfs(n-1,i,box,visit,m,n);}}for (int i=0;i<n;i++){for(int j=0;j<m;j++){if(box[i][j]==1) box[i][j]=0;else if(box[i][j]==2) box[i][j]=1;printf("%d ",box[i][j]);}printf("\n");}return 0;
}

或者bfs：

int front=-1,rear=-1;
int queue[1000][2];void bfs(int i,int j,int**box,int **visit,int m,int n){rear++;queue[rear][0]=i;queue[rear][1]=j;visit[i][j]=1;box[i][j]=2;while(rear!=front){front++;int xi=queue[front][0];int xj=queue[front][1];for(int k=0;k<4;k++){int movei=xi+move[k][0];int movej=xj+move[k][1];if(movei>=0 && movej>=0 && movei<n && movej<m && visit[movei][movej]==0 && box[movei][movej]==1){rear++;queue[rear][0]=movei;queue[rear][1]=movej;visit[movei][movej]=1;box[movei][movej]=2;}}}}

 

103. 水流问题

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

题目描述：

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述：

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

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述：

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

分析：

一、从高往低寻找

小的数 无法继承大的数的遍历结果，导致每个数字都必须从头遍历，复杂度太高

遍历每一个节点，是 m * n，遍历每一个节点的时候，都要做深搜，深搜的时间复杂度是： m * n

那么整体时间复杂度 就是 O(m^2 * n^2) ，这是一个四次方的时间复杂度。

 二、从低往高

从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。

同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。

然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。

从第一组边界边上节点出发，如图：

从第二组边界上节点出发，如图：

关于dfs函数搜索的过程 时间复杂度是 O(n * m)，这个大家比较容易想。

关键看主函数，那么每次dfs的时候，上面还是有for循环的。

第一个for循环，时间复杂度是：n * (n * m) 。

第二个for循环，时间复杂度是：m * (n * m)。

所以本题看起来 时间复杂度好像是 ： n * (n * m) + m * (n * m) = (m * n) * (m + n) 。

其实这是一个误区，大家再自己看 dfs函数的实现，其实 有visited函数记录 走过的节点，而走过的节点是不会再走第二次的。

所以 调用dfs函数，只要参数传入的是 数组 firstBorder，那么地图中 每一个节点其实就遍历一次，无论你调用多少次。

同理，调用dfs函数，只要 参数传入的是 数组 secondBorder，地图中每个节点也只会遍历一次。

所以，以下这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次，参数传入 firstBorder 的时候遍历一次，参数传入 secondBorder 的时候遍历一次。

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h>
#include <string.h>int move[4][2]={1,0,0,1,-1,0,0,-1};int main(){int n,m;scanf("%d%d",&n,&m);int** box=(int**)malloc(sizeof(int*)*n);int **visit1=(int**)malloc(sizeof(int*)*n);int **visit2=(int**)malloc(sizeof(int*)*n);for (int i=0;i<n;i++){box[i]=(int*)malloc(sizeof(int)*m);visit1[i]=(int*)malloc(sizeof(int)*m);visit2[i]=(int*)malloc(sizeof(int)*m);for(int j=0;j<m;j++){scanf("%d",&box[i][j]);visit1[i][j]=0;visit2[i][j]=0;}}for (int i=0;i<n;i++){if(visit1[i][0]==0) dfs(i,0,box,visit1,m,n);if(visit2[i][m-1]==0) dfs(i,m-1,box,visit2,m,n);  }for (int i=0;i<m;i++){if(visit1[0][i]==0) dfs(0,i,box,visit1,m,n);if( visit2[n-1][i]==0) dfs(n-1,i,box,visit2,m,n);}for (int i=0;i<n;i++){for(int j=0;j<m;j++){if(visit1[i][j]==1 && visit2[i][j]==1) printf("%d %d\n",i,j);            }}return 0;
}

bfs:

int front=-1,rear=-1;
int queue[1000][2];void bfs(int i,int j,int**box,int **visit,int m,int n){rear++;queue[rear][0]=i;queue[rear][1]=j;visit[i][j]=1;while(rear!=front){front++;int xi=queue[front][0];int xj=queue[front][1];for(int k=0;k<4;k++){int movei=xi+move[k][0];int movej=xj+move[k][1];if(movei>=0 && movej>=0 && movei<n && movej<m && visit[movei][movej]==0 && box[movei][movej]>=box[xi][xj]){rear++;queue[rear][0]=movei;queue[rear][1]=movej;visit[movei][movej]=1;}}}}