0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

DFS算法秒杀五道岛屿系列问题

jf_78858299 来源:labuladong 作者:labuladong 2023-04-19 10:39 次阅读

岛屿问题是经典的面试高频题,虽然基本的岛屿问题并不难,但是岛屿问题有一些有意思的扩展,比如求子岛屿数量,求形状不同的岛屿数量等等,本文就来把这些问题一网打尽。

岛屿系列问题的核心考点就是用 DFS/BFS 算法遍历二维数组

本文主要来讲解如何用 DFS 算法来秒杀岛屿系列问题,不过用 BFS 算法的核心思路是完全一样的,无非就是把 DFS 改写成 BFS 而已。

那么如何在二维矩阵中使用 DFS 搜索呢?如果你把二维矩阵中的每一个位置看做一个节点,这个节点的上下左右四个位置就是相邻节点,那么整个矩阵就可以抽象成一幅网状的「图」结构。

根据 [学习数据结构和算法的框架思维],完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架:

// 二叉树遍历框架
void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }
    // 前序:进入节点 (i, j)
    visited[i][j] = true;
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
    // 后序:离开节点 (i, j)
    // visited[i][j] = true;
}

因为二维矩阵本质上是一幅「图」,所以遍历的过程中需要一个visited布尔数组防止走回头路,如果你能理解上面这段代码,那么搞定所有岛屿问题都很简单。

这里额外说一个处理二维数组的常用小技巧,你有时会看到使用「方向数组」来处理上下左右的遍历,和前文 [图遍历框架]的代码很类似:

// 方向数组,分别代表上、下、左、右
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

void dfs(int[][] grid, int i, int j, boolean[] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }

    // 进入节点 (i, j)
    visited[i][j] = true;
    // 递归遍历上下左右的节点
    for (int[] d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j);
    }
    // 离开节点 (i, j)
    // visited[i][j] = true;
}

这种写法无非就是用 for 循环处理上下左右的遍历罢了,你可以按照个人喜好选择写法。

岛屿数量

这是力扣第 200 题「岛屿数量」,最简单也是最经典的一道岛屿问题,题目会输入一个二维数组grid,其中只包含0或者10代表海水,1代表陆地,且假设该矩阵四周都是被海水包围着的。

我们说连成片的陆地形成岛屿,那么请你写一个算法,计算这个矩阵grid中岛屿的个数,函数签名如下:

int numIslands(char[][] grid);

比如说题目给你输入下面这个grid有四片岛屿,算法应该返回 4:

图片

思路很简单,关键在于如何寻找并标记「岛屿」,这就要 DFS 算法发挥作用了,我们直接看解法代码:

// 主函数,计算岛屿数量
int numIslands(char[][] grid) {
    int res = 0;
    int m = grid.length, n = grid[0].length;
    // 遍历 grid
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                // 每发现一个岛屿,岛屿数量加一
                res++;
                // 然后使用 DFS 将岛屿淹了
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的陆地都变成海水
void dfs(char[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (grid[i][j] == '0') {
        // 已经是海水了
        return;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = '0';
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

为什么每次遇到岛屿,都要用 DFS 算法把岛屿「淹了」呢?主要是为了省事,避免维护visited数组

因为dfs函数遍历到值为0的位置会直接返回,所以只要把经过的位置都设置为0,就可以起到不走回头路的作用。

PS:这类 DFS 算法还有个别名叫做 [FloodFill 算法],现在有没有觉得 FloodFill 这个名字还挺贴切的~

这个最最基本的岛屿问题就说到这,我们来看看后面的题目有什么花样。

封闭岛屿的数量

上一题说二维矩阵四周可以认为也是被海水包围的,所以靠边的陆地也算作岛屿。

力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同:

1、用0表示陆地,用1表示海水。

2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被1包围的0,也就是说 靠边的陆地不算作「封闭岛屿」

函数签名如下:

int closedIsland(int[][] grid)

比如题目给你输入如下这个二维矩阵:

图片

算法返回 2,只有图中灰色部分的0是四周全都被海水包围着的「封闭岛屿」。

那么如何判断「封闭岛屿」呢?其实很简单,把上一题中那些靠边的岛屿排除掉,剩下的不就是「封闭岛屿」了吗

有了这个思路,就可以直接看代码了,注意这题规定0表示陆地,用1表示海水:

// 主函数:计算封闭岛屿的数量
int closedIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int j = 0; j < n; j++) {
        // 把靠上边的岛屿淹掉
        dfs(grid, 0, j);
        // 把靠下边的岛屿淹掉
        dfs(grid, m - 1, j);
    }
    for (int i = 0; i < m; i++) {
        // 把靠左边的岛屿淹掉
        dfs(grid, i, 0);
        // 把靠右边的岛屿淹掉
        dfs(grid, i, n - 1);
    }
    // 遍历 grid,剩下的岛屿都是封闭岛屿
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的陆地都变成海水
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (grid[i][j] == 1) {
        // 已经是海水了
        return;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 1;
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

只要提前把靠边的陆地都淹掉,然后算出来的就是封闭岛屿了。

PS:处理这类岛屿问题除了 DFS/BFS 算法之外,Union Find 并查集算法也是一种可选的方法,前文 [Union Find 算法运用] 就用 Union Find 算法解决了一道类似的问题。

这道岛屿题目的解法稍微改改就可以解决力扣第 1020 题「飞地的数量」,这题不让你求封闭岛屿的数量,而是求封闭岛屿的面积总和。

其实思路都是一样的,先把靠边的陆地淹掉,然后去数剩下的陆地数量就行了,注意第 1020 题中1代表陆地,0代表海水:

int numEnclaves(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // 淹掉靠边的陆地
    for (int i = 0; i < m; i++) {
        dfs(grid, i, 0);
        dfs(grid, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        dfs(grid, 0, j);
        dfs(grid, m - 1, j);
    }

    // 数一数剩下的陆地
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                res += 1;
            }
        }
    }

    return res;
}

// 和之前的实现类似
void dfs(int[][] grid, int i, int j) {
    // ...
}

篇幅所限,具体代码我就不写了,我们继续看其他的岛屿问题。

岛屿的最大面积

这是力扣第 695 题「岛屿的最大面积」,0表示海水,1表示陆地,现在不让你计算岛屿的个数了,而是让你计算最大的那个岛屿的面积,函数签名如下:

int maxAreaOfIsland(int[][] grid)

比如题目给你输入如下一个二维矩阵:

图片

其中面积最大的是橘红色的岛屿,算法返回它的面积 6。

这题的大体思路和之前完全一样,只不过dfs函数淹没岛屿的同时,还应该想办法记录这个岛屿的面积

我们可以给dfs函数设置返回值,记录每次淹没的陆地的个数,直接看解法吧:

int maxAreaOfIsland(int[][] grid) {
    // 记录岛屿的最大面积
    int res = 0;
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                // 淹没岛屿,并更新最大岛屿面积
                res = Math.max(res, dfs(grid, i, j));
            }
        }
    }
    return res;
}

// 淹没与 (i, j) 相邻的陆地,并返回淹没的陆地面积
int dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return 0;
    }
    if (grid[i][j] == 0) {
        // 已经是海水了
        return 0;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 0;

    return dfs(grid, i + 1, j)
         + dfs(grid, i, j + 1)
         + dfs(grid, i - 1, j)
         + dfs(grid, i, j - 1) + 1;
}

解法和之前相比差不多,我也不多说了,接下来的两道岛屿问题是比较有技巧性的,我们重点来看一下。

子岛屿数量

如果说前面的题目都是模板题,那么力扣第 1905 题「统计子岛屿」可能得动动脑子了:

图片

这道题的关键在于,如何快速判断子岛屿 ?肯定可以借助 [Union Find 并查集算法] 来判断,不过本文重点在 DFS 算法,就不展开并查集算法了。

什么情况下grid2中的一个岛屿Bgrid1中的一个岛屿A的子岛?

当岛屿B中所有陆地在岛屿A中也是陆地的时候,岛屿B是岛屿A的子岛。

反过来说,如果岛屿B中存在一片陆地,在岛屿A的对应位置是海水,那么岛屿B就不是岛屿A的子岛

那么,我们只要遍历grid2中的所有岛屿,把那些不可能是子岛的岛屿排除掉,剩下的就是子岛。

依据这个思路,可以直接写出下面的代码:

int countSubIslands(int[][] grid1, int[][] grid2) {
    int m = grid1.length, n = grid1[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid1[i][j] == 0 && grid2[i][j] == 1) {
                // 这个岛屿肯定不是子岛,淹掉
                dfs(grid2, i, j);
            }
        }
    }
    // 现在 grid2 中剩下的岛屿都是子岛,计算岛屿数量
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid2[i][j] == 1) {
                res++;
                dfs(grid2, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始,将与之相邻的陆地都变成海水
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (grid[i][j] == 0) {
        return;
    }

    grid[i][j] = 0;
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

这道题的思路和计算「封闭岛屿」数量的思路有些类似,只不过后者排除那些靠边的岛屿,前者排除那些不可能是子岛的岛屿。

不同的岛屿数量

这是本文的最后一道岛屿题目,作为压轴题,当然是最有意思的。

力扣第 694 题「不同的岛屿数量」,题目还是输入一个二维矩阵,0表示海水,1表示陆地,这次让你计算 不同的 (distinct) 岛屿数量,函数签名如下:

int numDistinctIslands(int[][] grid)

比如题目输入下面这个二维矩阵:

图片

其中有四个岛屿,但是左下角和右上角的岛屿形状相同,所以不同的岛屿共有三个,算法返回 3。

很显然我们得想办法把二维矩阵中的「岛屿」进行转化,变成比如字符串这样的类型,然后利用 HashSet 这样的数据结构去重,最终得到不同的岛屿的个数。

如果想把岛屿转化成字符串,说白了就是序列化,序列化说白了遍历嘛,前文 [二叉树的序列化和反序列化]讲了二叉树和字符串互转,这里也是类似的。

首先,对于形状相同的岛屿,如果从同一起点出发,dfs函数遍历的顺序肯定是一样的

因为遍历顺序是写死在你的递归函数里面的,不会动态改变:

void dfs(int[][] grid, int i, int j) {
    // 递归顺序:
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

所以,遍历顺序从某种意义上说就可以用来描述岛屿的形状,比如下图这两个岛屿:

图片

假设它们的遍历顺序是:

下,右,上,撤销上,撤销右,撤销下

如果我用分别用1, 2, 3, 4代表上下左右,用-1, -2, -3, -4代表上下左右的撤销,那么可以这样表示它们的遍历顺序:

2, 4, 1, -1, -4, -2

你看,这就相当于是岛屿序列化的结果,只要每次使用dfs遍历岛屿的时候生成这串数字进行比较,就可以计算到底有多少个不同的岛屿了

要想生成这段数字,需要稍微改造dfs函数,添加一些函数参数以便记录遍历顺序:

void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n 
        || grid[i][j] == 0) {
        return;
    }
    // 前序遍历位置:进入 (i, j)
    grid[i][j] = 0;
    sb.append(dir).append(',');

    dfs(grid, i - 1, j, sb, 1); // 上
    dfs(grid, i + 1, j, sb, 2); // 下
    dfs(grid, i, j - 1, sb, 3); // 左
    dfs(grid, i, j + 1, sb, 4); // 右

    // 后序遍历位置:离开 (i, j)
    sb.append(-dir).append(',');
}

dir记录方向,dfs函数递归结束后,sb记录着整个遍历顺序,其实这就是前文 [回溯算法核心套路]说到的回溯算法框架,你看到头来这些算法都是相通的。

有了这个dfs函数就好办了,我们可以直接写出最后的解法代码:

int numDistinctIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // 记录所有岛屿的序列化结果
    HashSet

这样,这道题就解决了,至于为什么初始调用dfs函数时的dir参数可以随意写,这里涉及 DFS 和回溯算法的一个细微差别,前文 [图算法基础]有写,这里就不展开了。

以上就是全部岛屿系列问题的解题思路,也许前面的题目大部分人会做,但是最后两题还是比较巧妙的,希望本文对你有帮助。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 数据结构
    +关注

    关注

    3

    文章

    573

    浏览量

    40127
  • DFS
    DFS
    +关注

    关注

    0

    文章

    26

    浏览量

    9163
  • BFS
    BFS
    +关注

    关注

    0

    文章

    9

    浏览量

    2170
收藏 人收藏

    评论

    相关推荐

    智能硬件欲起飞?必须跨越这五道门槛

    9月20日,笔者受邀参加一个智能硬件线下沙龙,来自智能硬件生产、研发、销售领域的几位资深人士分享了自己对行业、产品的看法。笔者结合沙龙分享及自身了解总结出,智能硬件从热捧到热卖还差五道坎。##行业发展是有规律的、循序渐进的。大到产业发展,小到一项威廉希尔官方网站 创新、产品创新被用户广泛接受,都需要一定的时间。
    发表于 09-23 09:59 668次阅读

    单片机8031三题:三、四、。一题10元

    单片机8031三题:三、四、。一题10元,直接发我qq840921270 ,会给第一个采用的人直接发支付宝,决不食言,食言剁屌!求助大神,小弟谢过了
    发表于 04-16 17:02

    经典算法大全(51个C语言算法+单片机常用算法+机器学十大算法

    、dynamic programming  四、BFS和DFS优先搜索算法  、红黑树算法的实现与剖析  (续)、教你透彻了解红黑树  
    发表于 10-23 14:31

    PCB生产工艺 | 第五道主流程之图形转移

    衔接上文,继续为朋友们分享普通单双面板的生产工艺流程。如图,第五道主流程为图形转移。图形转移的目的为:利用光化学原理,将图形线路的形状转移到印制板上,再利用化学原理,将图形线路在印制板上制作
    发表于 02-17 11:46

    安防企业转型升级过程中还需要攻克这五道关口

    。在这个过程中,对于众多安防企业来说,选择成为最重要的事情,企业家眼光既要向外,看到市场变化及趋势;又要向内,审视企业自身优势和竞争力。在转型升级过程中,安防企业需要攻克五道关口。
    发表于 08-27 16:44 842次阅读

    RT-Thread DFS 组件的主要功能特点

    DFS 的层次架构如下图所示,主要分为 POSIX 接口层、虚拟文件系统层和设备抽象层。
    发表于 07-08 15:29 4662次阅读

    一篇文章秒杀区间相关的问题

    经常有读者问区间相关的问题,今天写一篇文章,秒杀区间相关的问题。 所谓区间问题,就是线段问题,让你合并所有线段、找出线段的交集等等。主要有两个技巧: 1、排序。常见的排序方法就是按照区间起点排序
    的头像 发表于 10-12 14:54 1897次阅读
    一篇文章<b class='flag-5'>秒杀</b>三<b class='flag-5'>道</b>区间相关的问题

    网络通讯厂商:深圳市和芯润德科技有限公司简介

    地址:深圳市南山区粤兴五道北理工创新大厦三楼A单元
    的头像 发表于 04-16 11:01 1855次阅读

    秒杀几道运用Dijkstra算法的题目

    ,变得看起来好像特别复杂,特别牛逼。 但如果你看过历史文章,应该可以对算法形成自己的理解,就会发现很多算法都是换汤不换药,毫无新意,非常枯燥。 比如,我们说二叉树非常重要,你把这个结构掌握了,就会发现 动态规划,分治算法,回溯(
    的头像 发表于 09-24 10:59 2944次阅读
    <b class='flag-5'>秒杀</b>几道运用Dijkstra<b class='flag-5'>算法</b>的题目

    如何用DFS算法秒杀岛屿系列问题

    DFS/BFS 算法遍历二维数组 。 本文主要来讲解如何用 DFS 算法秒杀岛屿
    的头像 发表于 11-16 17:13 1753次阅读
    如何用<b class='flag-5'>DFS</b><b class='flag-5'>算法</b>来<b class='flag-5'>秒杀</b><b class='flag-5'>岛屿</b><b class='flag-5'>系列</b>问题

    DFS发布全球首个奢侈品旅游零售元宇宙,系列数字藏品限量发行

    中国时间2022年8月1日,世界知名奢侈品旅游零售商DFS集团正式发布全球首个奢华旅行零售元宇宙,牵手国内领先的数字藏品发行、推广及交易平台淘派发行系列限量数字藏品。 DFS集团始终以敏锐的潮流意识
    的头像 发表于 09-06 10:44 1504次阅读

    PCB生产工艺 | 第五道主流程之图形转移

    衔接上文,继续为朋友们分享普通单双面板的生产工艺流程。 如图,第五道主流程为图形转移。 图形转移的目的为: 利用光化学原理,将图形线路的形状转移到印制板上,再利用化学原理,将图形线路在印制板上制作
    的头像 发表于 02-16 21:00 2176次阅读

    【生产工艺】第五道主流程之图形转移

    衔接上文,继续为朋友们分享普通单双面板的生产工艺流程。 如图,第五道主流程为图形转移。 图形转移的目的为: 利用光化学原理,将图形线路的形状转移到印制板上,再利用化学原理,将图形线路在印制板上制作
    的头像 发表于 04-06 09:20 1125次阅读

    滑动窗口算法解决子串问题教程

    本文详解「滑动窗口」这种高级双指针技巧的算法框架,带你秒杀几道高难度的子字符串匹配问题。 LeetCode 上至少有 9 题目可以用此方法高效解决。但是有几道是 VIP 题目,有几道题目虽不
    的头像 发表于 04-19 11:06 744次阅读
    滑动窗口<b class='flag-5'>算法</b>解决子串问题教程

    清华五道口全球科技与金融发展学者团来本源量子参观交流

    9月2日,清华五道口全球科技与金融发展学者们来到本源量子参观交流。各位学员来到本源量子计算体验中心,在云中心徐老师的陪同下进行了参观,不仅看到了国内首批工程化的量子计算机,还通过介绍了解到本源量子在
    的头像 发表于 09-07 09:48 576次阅读
    清华<b class='flag-5'>五道</b>口全球科技与金融发展学者团来本源量子参观交流