计数子岛

2024-08-29 0 807

1905 年。计算子岛屿

难度:中等

主题:数组、深度优先搜索、广度优先搜索、并集查找、矩阵

给定两个 m x n 二进制矩阵 grid1 和 grid2,其中仅包含 0(代表水)和 1(代表土地)。 岛屿是一组由1连接的4向(水平或垂直)。网格之外的任何细胞都被视为水细胞。

如果 grid1 中的一个岛包含所有构成 grid2 中这个岛的单元格,则 grid2 中的岛被视为子岛 .

返回grid2中被视为子岛数量个岛屿。

示例1:

计数子岛

  • 输入: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1, 0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[ 0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
  • 输出: 3
  • 说明
    • 上图中,左边的网格是grid1,右边的网格是grid2。
    • grid2 中红色的 1 被认为是子岛的一部分。共有三个子岛。

示例2:

计数子岛

  • 输入: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1, 1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[ 0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
  • 输出: 2
  • 说明
    • 上图中,左边的网格是grid1,右边的网格是grid2。
    • grid2 中红色的 1 被认为是子岛的一部分。有两个子岛。

约束:

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1
  • grid1[i][j] 和 grid2[i][j] 为 0 或 1。

提示:

  1. 让我们使用洪水填充来迭代第二个网格的岛屿
  2. 让我们注意,如果第二个网格中的一个岛上的所有单元格都由第一个网格中的土地表示,那么它们就会连接起来,从而使该岛成为一个子岛

解决方案:

我们将使用深度优先搜索 (dfs) 方法来探索 grid2 中的岛屿,并检查每个岛屿是否完全包含在 grid1 中的相应岛屿内。以下是我们实施该解决方案的方法:

步骤:

  1. 遍历网格:我们将迭代 grid2 中的每个单元格。
  2. 识别 grid2 中的岛屿:当我们在 grid2 中遇到陆地单元 (1) 时,我们将使用 dfs 探索整个岛屿。
  3. 检查子岛情况: 在 grid2 中的一个岛屿上执行 dfs 时,我们将检查 grid1 中所有对应的单元格是否也是陆地单元格。如果是的话,该岛就是一个子岛。
  4. 计算子岛数: 对于 grid2 中满足子岛条件的每个岛屿,我们将增加子岛数。

让我们用 php 实现这个解决方案:1905。数一下子岛屿

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

<?php /**

 * @param $grid1

 * @param $grid2

 * @return int

 */

function countSubIslands($grid1, $grid2) {

    ...

    ...

    ...

    /**

     * go to ./solution.php

     */

}

/**

 * @param $grid1

 * @param $grid2

 * @param $i

 * @param $j

 * @param $m

 * @param $n

 * @return int|true

 */

function dfs(&$grid1, &$grid2, $i, $j, $m, $n) {

    ...

    ...

    ...

    /**

     * go to ./solution.php

     */

}

// Example usage:

// Example 1

$grid1 = [

    [1,1,1,0,0],

    [0,1,1,1,1],

    [0,0,0,0,0],

    [1,0,0,0,0],

    [1,1,0,1,1]

];

$grid2 = [

    [1,1,1,0,0],

    [0,0,1,1,1],

    [0,1,0,0,0],

    [1,0,1,1,0],

    [0,1,0,1,0]

];

echo countSubIslands($grid1, $grid2); // Output: 3

// Example 2

$grid1 = [

    [1,0,1,0,1],

    [1,1,1,1,1],

    [0,0,0,0,0],

    [1,1,1,1,1],

    [1,0,1,0,1]

];

$grid2 = [

    [0,0,0,0,0],

    [1,1,1,1,1],

    [0,1,0,1,0],

    [0,1,0,1,0],

    [1,0,0,0,1]

];

echo countSubIslands($grid1, $grid2); // Output: 2

?>

解释:

  • dfs 函数: dfs 函数探索 grid2 中的岛屿,并检查 grid1 中相应的单元格是否都是陆地单元格。如果 grid2 中的任何单元格是陆地,但 grid1 中相应的单元格是水,则 grid2 中的岛屿不是子岛。
  • 标记已访问: 当我们遍历 grid2 时,我们通过将单元格设置为 0 将其标记为已访问。
  • 主循环:我们迭代grid2中的所有单元格。每当我们发现一个尚未访问过的陆地单元时,我们都会启动 dfs 来检查它是否是子岛的一部分。

时间复杂度:

时间复杂度为 (o(m × n)),其中 m 是行数,n 是列数。这是因为我们可能会访问每个单元格一次。

该解决方案应该在给定的限制内有效地工作

收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

免责声明
1. 本站所有资源来源于用户上传和网络等,如有侵权请邮件联系本站整改team@lcwl.fun!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系本站工作人员处理!
6. 本站资源售价或VIP只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!
8. 因人力时间成本问题,部分源码未能详细测试(解密),不能分辨部分源码是病毒还是误报,所以没有进行任何修改,大家使用前请进行甄别!
9.本站所有源码资源都是经过本站工作人员人工亲测可搭建的,保证每个源码都可以正常搭建,但不保证源码内功能都完全可用,源码属于可复制的产品,无任何理由退款!

网站搭建学习网 PHP 计数子岛 https://www.xuezuoweb.com/15279.html

常见问题
  • 本站所有的源码都是经过平台人工部署搭建测试过可用的
查看详情
  • 购买源码资源时购买了带主机的套餐是指可以享受源码和所选套餐型号的主机两个产品,在本站套餐里开通主机可享优惠,最高免费使用主机
查看详情

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务

Fa快捷助手
手机编程软件开发

在手机上用手点一点就能轻松做软件

去做软件
链未云主机
免备案香港云主机

开通主机就送域名的免备案香港云主机

去使用
链未云服务器
免备案香港云服务器

支持售后、超低价、稳定的免备案香港云服务器

去使用