1905 年。计算子岛屿
难度:中等
主题:数组、深度优先搜索、广度优先搜索、并集查找、矩阵
给定两个 m x n 二进制矩阵 grid1 和 grid2,其中仅包含 0(代表水)和 1(代表土地)。 岛屿是一组由1连接的4向(水平或垂直)。网格之外的任何细胞都被视为水细胞。
如果 grid1 中的一个岛包含所有构成 grid2 中这个岛的单元格,则 grid2 中的岛被视为子岛 .
返回grid2中被视为子岛的数量个岛屿。
示例1:
示例2:
约束:
提示:
解决方案:
我们将使用深度优先搜索 (DFS) 方法来探索 grid2 中的岛屿,并检查每个岛屿是否完全包含在 grid1 中的相应岛屿内。以下是我们如何实施该解决方案:
让我们用 PHP 实现这个解决方案:1905。数一下子岛屿
<?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 ?>
时间复杂度为 (O(m × n)),其中 m 是行数,n 是列数。这是因为我们可能会访问每个单元格一次。
该解决方案应该在给定的限制内有效地工作。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
以上是计数子岛的详细内容。更多信息请关注PHP中文网其他相关文章!