DEV Community
·
1905. 统计子岛屿数量
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定两个二进制矩阵grid1和grid2，表示陆地和水域，判断grid2中的岛屿是否是grid1中岛屿的子岛屿。使用DFS遍历grid2中的岛屿，检查对应的grid1中的岛屿是否都是陆地。返回满足子岛屿条件的岛屿数量。
🎯
关键要点
- 给定两个二进制矩阵grid1和grid2，表示陆地和水域。
- 岛屿是连接的1的组，任何超出矩阵的单元格被视为水域。
- grid2中的岛屿被视为子岛屿，如果grid1中有一个岛屿包含grid2中该岛屿的所有单元格。
- 返回grid2中被视为子岛屿的岛屿数量。
- 使用深度优先搜索（DFS）遍历grid2中的岛屿，检查对应的grid1中的岛屿是否都是陆地。
- 遍历grid2中的每个单元格，识别岛屿并进行DFS探索。
- 在DFS过程中检查grid1中对应的单元格是否都是陆地，如果是，则该岛屿为子岛屿。
- 每找到一个满足子岛屿条件的岛屿，计数加一。
- 时间复杂度为O(m × n)，其中m为行数，n为列数。
➡️
