岛屿类网格问题的通用解法——dfs遍历网格
我们所熟悉的DFS问题通常是在树或者图上进行的，
新的DFS——网格上进行，如岛屿问题，
一、网格问题的基本概念
- ==网格问题是有m*n个小方格组成的网络，每个小方格与其上下左右四个方格是相邻的，要在这样的网格上进行某种搜索。==
- 岛屿问题是一类典型的网格问题，每个格子中的数字可能是0或者1，
我们把数字为0的格子看成海洋格子，数字为1的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。
二、DFS的基本结构
1.二叉树dfs遍历方法
网格问题要比二叉树结构稍微复杂一些，它其实是简化版的图结构。
要写好网格上的dfs遍历，首先要理解二叉树dfs遍历方法。
void treeTraverse(TreeNode root){
//判断base case
if(root==null) return;
//访问相邻节点：左子节点，右子节点
treeTraverse(root.left);
treeTraverse(root.right);
}
复制代码可以看到，二叉树的DFS有两个要素：
- 访问相邻节点
二叉树相邻节点非常简单，只有左子节点和右子节点两个。
二叉树本身就是一个递归定义的结构：一棵二叉树，它的左子树和右子树本身也是一棵二叉树，我们的DFS遍历只需要递归调用左子树和右子树即可。
- 判断basecase
一般来说，二叉树遍历的base case是root == null。两个含义：
①表示指向的子树为空，不需要再往下遍历了
②在root==null时及时返回，可以让后面的root.left和root.right操作不会出现空指针异常。
2.网格上的DFS——参考二叉树dfs
- 网格上的格子的相邻节点
有上下左右四个相邻节点；对于格子(r,c)而言，四个相邻的格子分别是(r-1,c),(r+1,c),(r,c-1),(r,c+1);
网络结构是“四叉”的
- 网格dfs中的base case
从二叉树的base case对应过来，应该是网格中不需要继续遍历，grid[r][c]会出现数组下标越界异常的格子
也就是那些超出网格范围的格子
判断base case，如果坐标超出网格范围，越界返回
if(r<0||r>grid.length||c<0||c>grid[0].length) return;
理解“坐标可以临时超出网格的范围”：
“先污染，后治理”——甭管当前是在哪个格子，先往四个方向走一步再说，如果发现走出了网格范围，再赶紧返回。
这跟二叉树遍历方法是一样的，先递归调用，发现root==null再返回。
这样，我们得到了==网格dfs遍历==的“框架代码”：
/*
*gird 网格二维矩阵数组
* r，c 当前处理网格的横纵坐标
*/
void dfs(char[][] grid,int r,int c){
//判断base case，如果坐标超出网格范围，越界返回
if(r<0||r>grid.length||c<0||c>grid[0].length) return;
//访问上、下、左、右、四个相邻节点
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(gird,r,c+1);
}
复制代码3.如何避免重复遍历
网格结构的dfs和二叉树dfs最大不同之处——遍历中可能遇到遍历过的节点。
这是因为网格结构本质上是一个图，我们可以把每个各自看成图中的节点，每个节点有向“上下左右”的四条边。
在图中遍历时，自然可能遇到重复遍历的节点。这时dfs就会不停的“兜圈子”，永远停不下来，如下图
- 如何避免重复遍历——==标记已经遍历过的格子==
以岛屿问题为例，
我们需要在所有值为1的陆地格子上左dfs遍历，每走过一个陆地格子，就把值设为2，
这样当我们遇到2的时候，就知道这是一个遍历过的格子。
即每个格子可能取三个值：
- 0——海洋格子
- 1——陆地格子（未遍历过）
- 2——陆地格子（已遍历过）
- ★★★★我们在框架代码中加入避免重复遍历的语句
void dfs(char[][] grid,int r,int c){
//1.判断base case，如果坐标超出网格范围，越界返回
if(r<0||r>grid.length||c<0||c>grid[0].length) return;
//【新】2.如果这个格子不是岛屿，是海洋或者已经访问过的岛屿，返回
if(grid[r][c]!='1') return;
//【新】3.是未访问过的岛屿
grid[r][c]='2';//标记为已经访问过
//再访问上、下、左、右、四个相邻节点
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(gird,r,c+1);
}
复制代码这样，我们就达到一个岛屿问题、乃至各种网格问题的通用dfs遍历方法。
** 小贴士：**
在一些题解中，可能会把“已遍历过的陆地格子”标记为和海洋个字一样的0，美其名曰“陆地沉没方法”；
但是这样不好，无法区分“海洋格子”和“已遍历过的陆地格子”了，
如果题目更复杂一点，很容易出bug。
三、例题
1.岛屿数量
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0) return 0;
int num_islands=0;
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
if(grid[r][c]!='1') continue;//【关键】遍历时不适合的节点直接跳过回溯
++num_islands;//【关键】出现适合的节点，只要出现了一个1，就代表有一个岛屿，而且这个岛屿至少有一个陆地；dfs标记它所有的陆地
dfs(grid,r,c);
}
}
return num_islands;
}
public void dfs(char[][] grid,int r,int c){
//1.判断base case:不在网格中，越界返回
if(r<0||r>=grid.length||c<0||c>=grid[0].length) return;
//2.如果这个格子不是岛屿，是海洋或者已经访问过的岛屿，返回
if(grid[r][c]!='1') return;
//3.是未访问过的岛屿
grid[r][c]='2';//标记为已经访问过
//访问上、下、左、右四个相邻节点，递归
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(grid,r,c+1);
}
}
复制代码2.最大岛屿的面积
所有岛屿中，最大岛屿的面积
/*
【岛屿最大面积】
相对于【岛屿数量】变形之处：
1.对每个岛屿做dfs时，求出每个岛屿的面积。
2.求岛屿面积的方法也很简单——每遍历到一个陆地格子，就把面积加一
*/
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int maxnum=0;
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
//海洋节点或者已访问节点跳过回溯
if(grid[r][c]!=1) continue;
//有效节点dfs，此处一次dfs可以发现一块陆地，计算一块陆地的面积
int curnum=dfs(grid,r,c);
maxnum=maxnum>curnum? maxnum:curnum;
}
}
return maxnum;
}
//每层dfs返回当前层节点在内的节点数量
public int dfs(int[][] grid,int r,int c){
//basecase越界返回
if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0;
//无效节点返回，海洋或已访问过
if(grid[r][c]!=1) return 0;
//有效节点，处理当前节点和dfs相邻节点
grid[r][c]=2;
return 1 //【关键】对返回当前层节点在内及dfs的有效节点数量
+dfs(grid,r-1,c)
+dfs(grid,r+1,c)
+dfs(grid,r,c-1)
+dfs(grid,r,c+1);
}
}
复制代码3.填海造陆 岛屿连接最大面积问题
易错：
/*
1. dfs寻找岛屿，为每个岛屿编号，并且在mark数组上为岛屿的每个陆地格子填入岛屿编号。
2. 一个岛屿遍历完成，采用map记录对应编号的岛屿的面积大小
3. 二维数组遍历，寻找海洋节点，查看每个海洋节点上下左右节点是否属于不同编号的岛屿；
如果是，填充此海洋节点，那么其周边的岛屿就可以连接起来，组成一个大的岛屿。
【易错】
1. 不一定只能连接两个岛屿，可以是多个岛屿
2. 注意上下左右可能是同一个岛屿的不同陆地格子，此时只能计算一次该岛屿
*/
class Solution {
public int largestIsland(int[][] grid) {
//1.找出每个岛屿，标记数组标记同一个岛屿
int[][] mark=new int[grid.length][grid[0].length];//初始化标记数组为0
//map存储每个岛屿的面积大小
Map<Integer,Integer> map=new HashMap<>();
//★★【关键】记录最大岛屿的面积
int maxsum=0;
//2.遍历，每个岛屿块标记和计数
int sign=3;//标记数组的编号
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
if(grid[r][c]!=1) continue;
int curnum=dfs(grid,r,c,mark,sign);//完成一个岛屿块的标记和计数
map.put(sign,curnum);
sign++;
maxsum=Math.max(maxsum,curnum);
}
}
//如果没有岛屿，那么可以填一个海洋格子
if(maxsum==0) return 1;
//3.有岛屿，重新遍历mark数组，计算每个海洋节点的相邻节点的最大值
for(int r=0;r<mark.length;r++){
for(int c=0;c<mark[0].length;c++){
//不是海洋节点跳过
if(mark[r][c]!=0) continue;
//★★★【关键】海洋节点，利用一个set选出海洋节点的相邻节点（此处set中存储岛屿编号，同一岛屿的陆地格子编号一致，不同岛屿的陆地格子不同
Set<Integer> set=getNeighborsSign(mark,r,c);
if(set.size()<1) continue;//海洋节点格子相邻节点没有陆地格子
int cursum=1;
for(int neighborSign:set){
cursum+=map.get(neighborSign);//利用编号去map中取出相应编号岛屿对应的面积大小
}
maxsum=Math.max(maxsum,cursum);
}
}
return maxsum;
}
//计算每个岛屿当前层及dfs的陆地格子个数，和标记岛屿
public int dfs(int[][] grid,int r,int c,int[][] mark,int sign){
if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0;
//无效节点返回，海洋或已访问过
if(grid[r][c]!=1) return 0;
//有效节点，处理当前节点和dfs相邻节点
grid[r][c]=2;
mark[r][c]=sign;//★★【关键】岛屿块的标记
return 1
+dfs(grid,r-1,c,mark,sign)
+dfs(grid,r+1,c,mark,sign)
+dfs(grid,r,c-1,mark,sign)
+dfs(grid,r,c+1,mark,sign);
}
//★★寻找每个海洋节点相邻节点的岛屿编号
public Set<Integer> getNeighborsSign(int[][] mark,int r,int c){
Set<Integer> set=new HashSet<>();
//相邻节点须在mark中，并且为岛屿节点mark[r][c]!=0;上下左右
if(r-1>=0&&mark[r-1][c]!=0) set.add(mark[r-1][c]);
if(r+1<mark.length&&mark[r+1][c]!=0) set.add(mark[r+1][c]);
if(c-1>=0&&mark[r][c-1]!=0) set.add(mark[r][c-1]);
if(c+1<mark.length&&mark[r][c+1]!=0) set.add(mark[r][c+1]);
return set;
}
}
复制代码4.岛屿的周长
、
- 网格DFS遍历的基本框架，dfs函数直接返回情况
情况一：节点越界，超出网格的范围
if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 0;
情况二：grid[r][c] != 1，即当前格子不是岛屿格子，这又分为两种情况：
①grid[r][c]==0,当前格子时海洋格子
②grid[r][c]==2,当前格子时已遍历的陆地格子
复制代码- 岛屿周长是计算岛屿全部的边缘，而这些边缘就是dfs遍历中，dfs函数返回的位置
我们将岛屿周长中的边分为两类：
- 黄色的边是与网格边界相邻的周长的边
- 蓝色的边是与海洋格子相邻的周长的边
- 算法思想：
- 当我们的dfs函数因为==网格坐标越界==返回的时候，实际上就经历了一条黄色的边；
- 当dfs函数因为==当前格子是海洋格子==返回的时候，实际上就经过了一条蓝色的边。
此时我们就将==岛屿周长的边==和==dfs遍历==联系起来了
/*方法一
网格dfs+回溯
*/
class Solution {
public int islandPerimeter(int[][] grid) {
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
//前面海洋节点的处理
if(grid[r][c]==0) continue;
//第一个有效陆地节点，遍历岛屿块；题目限制只有一个岛屿，所以直接返回
return dfs(grid,r,c);
}
}
return 0;
}
public int dfs(int[][] grid,int r,int c){
//【关键】1.当访问节点越界时，代表一种遇到一个边的情况
if(r<0||r>=grid.length||c<0||c>=grid[0].length) return 1;
//无效节点:海洋节点、已遍历过的节点
//【关键】2.当访问节点是海洋格子时，代表一种遇到一个边的情况
if(grid[r][c]==0) return 1;
//当访问节点时已遍历过的节点，此时非边
if(grid[r][c]==2) return 0;
//未遍历过的节点处理
grid[r][c]=2;
return dfs(grid,r-1,c)
+dfs(grid,r+1,c)
+dfs(grid,r,c-1)
+dfs(grid,r,c+1);
}
}
/*
方法二：迭代
对于一个陆地格子的每条边，只有当这条边是：
1. 网格的边界
2. 相邻的另一个格子为海洋格子
算法：遍历每个陆地格子，看其四个方向是否为边界或者海洋格子，如果是，ret++
*/
class Solution {
public int islandPerimeter(int[][] grid) {
//坐标变换数组
int[] dx={-1,1,0,0};
int[] dy={0,0,-1,1};
int cnt=0;
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
//海洋节点跳过
if(grid[r][c]==0) continue;
//陆地格子节点,遍历相邻节点
for(int k=0;k<dx.length;k++){
int tx=r+dx[k];
int ty=c+dy[k];
//【关键】节点越界；海洋节点
if(tx<0||tx>=grid.length||ty<0||ty>=grid[0].length||grid[tx][ty]==0) cnt++;
}
}
}
return cnt;
}
}
复制代码四、访问相邻节点，坐标变换数组+for循环 处理
static int[] dx={-1,1,0,0};
statci int[] dy={0,0,-1,1};
for(int k=0;k<4;k++){
int tx=c+dx[k];
int ty=r+dy[k];
dfs(grid,tx,ty);
}
复制代码© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
