LeetCode 1905. 统计子岛屿

2026-09-13 HGNULB 约 6 分钟

文章信息 2 个分类 5 个标签

分类

LeetCode 中等

题目描述

✅ 1905. 统计子岛屿

题意分析

两张等大的二元网格中，一表示陆地，零表示水；岛屿由上下左右相连的陆地组成。若 grid2 中某个完整岛屿的全部格子，都落在 grid1 的同一个岛屿里，它就是子岛屿。

统计的是 grid2 的岛屿数量，而不是重合陆地格数。只要某个岛屿有一格在 grid1 中为水，整个岛屿都不合格，不能把剩余重合部分拆开后分别计数。

解法：完整遍历岛屿并累计包含条件

核心思路

[!blue]

先按 grid2 自己的连通关系，完整遍历每一座岛。遍历过程中只需检查对应的 grid1 格子是否全为陆地，不必先给 grid1 的岛屿编号。

这是因为 grid2 岛屿内任意两格都存在一条四方向陆地路径；如果路径上的每格在 grid1 中也都是陆地，同一条路径就在 grid1 中成立，所以这些格子必然属于 grid1 的同一个岛屿。逐格包含条件已经足够保证整体包含。

每次找到未访问陆地，就创建队列并令本岛 valid = true。格子入队时立即把 grid2 对应位置置零，作为访问标记；出队时检查 grid1，遇到水就把本岛标记改为 false。

标记失败以后仍要继续搜索所有与它相连的 grid2 陆地。失败只说明本岛不能计数，不代表遍历已经完成；若提前退出，剩下的同岛格子可能在外层扫描时被误当作另一座岛。

队列清空才表示原来的整个连通块都已处理完，此时根据 valid 决定是否加一。这样每座岛只被启动一次，不合格岛也会被完整标记；实现会修改 grid2，但始终只读取 grid1。

解题步骤

扫描 grid2，水或已访问格子直接跳过。

找到陆地时创建新岛搜索，初始标记为有效，起点入队并立即置零。

出队格子若对应 grid1 的水，将本岛标记为无效；继续把界内未访问的四邻陆地标记并入队。

无论标记是否已经失败，都处理到队列为空。

整岛遍历完成后，有效才增加答案，最后返回总数。

代码实现

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid2.length;
        int n = grid2[0].length;
        int answer = 0;
        int[] dirs = {
            -1,
            0,
            1,
            0,
            -1
        };

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid2[r][c] == 0) {
                    continue;
                }

                boolean valid = true;
                Deque<int[]> queue = new ArrayDeque<>();

                queue.add(new int[] {
                    r,
                    c
                });
                grid2[r][c] = 0;

                while (!queue.isEmpty()) {
                    int[] cell = queue.remove();

                    if (grid1[cell[0]][cell[1]] == 0) {
                        valid = false;
                    }

                    for (int d = 0; d < 4; d++) {
                        int x = cell[0] + dirs[d];
                        int y = cell[1] + dirs[d + 1];

                        if (x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1) {
                            grid2[x][y] = 0;
                            queue.add(new int[] {
                                x,
                                y
                            });
                        }
                    }
                }

                if (valid) {
                    answer++;
                }
            }
        }

        return answer;
    }
}

func countSubIslands(grid1, grid2 [][]int) int {
    m, n := len(grid2), len(grid2[0])
    answer := 0
    dirs := []int{
        -1,
        0,
        1,
        0,
        -1,
    }
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if grid2[r][c] == 0 {
                continue
            }
            valid := true
            queue := [][2]int{
                {
                    r,
                    c,
                },
            }
            grid2[r][c] = 0
            for head := 0; head < len(queue); head++ {
                cell := queue[head]
                if grid1[cell[0]][cell[1]] == 0 {
                    valid = false
                }
                for d := 0; d < 4; d++ {
                    x, y := cell[0]+dirs[d], cell[1]+dirs[d+1]
                    if x >= 0 && x < m && y >= 0 && y < n && grid2[x][y] == 1 {
                        grid2[x][y] = 0
                        queue = append(queue, [2]int{
                            x,
                            y,
                        })
                    }
                }
            }
            if valid {
                answer++
            }
        }
    }
    return answer
}

复杂度分析

设网格有 $m$ 行、$n$ 列。

时间复杂度：$O(mn)$，每个格子被外层检查一次，每块陆地最多入队、出队一次，并检查四个方向。

辅助空间复杂度：$O(mn)$，最坏用于岛屿搜索队列；访问标记直接写在 grid2 中。

关键点总结

[!green]

先按 grid2 划分完整岛屿，再检查所有格子是否被 grid1 覆盖。

四方向路径也被完整覆盖，便保证落在 grid1 同一岛屿，无需额外编号。

判定可以提前变为失败，遍历却不能提前停止。

入队即标记使每格只进入队列一次。

易错点总结

[!yellow]

遇到不匹配格子就立即 break 或返回，会留下同一岛屿的未访问部分，造成误计数。

先把所有不匹配格子删掉再数剩余岛，会改变原来的岛屿划分，不符合整岛判定。

不能只沿 grid1 为陆地的格子扩展，失败位置仍属于待完整访问的 grid2 岛屿。

只检查对角相邻不算连通，本题仅使用上下左右四个方向。

每座新岛都要重置 valid，但不应恢复已经置零的 grid2 访问标记。

相似题目

题目	难度	关联与区别
200. 岛屿数量	中等	复用整岛遍历和访问标记，在此基础上为每个岛增加对另一张网格的包含检查。
695. 岛屿的最大面积	中等	同样在一次连通块遍历中汇总结果，原题累计面积，本题累计全体格子的包含条件。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/54113701

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！