从公司WiFi监控聊到LeetCode 1905：子岛屿统计与DFS解题思路

最近在网上流传的一张“公司员工工作状态分析报告”截图，让不少打工人心头一紧。这张图通过网络分析，清晰地展示了全公司的平均工作占比、准时上线率，甚至细化到哪些IP地址的设备在工作期间频繁访问小红书、抖音、BOSS直聘等网站。

网友们纷纷评论：“这以后谁还敢连公司WiFi”。虽然我们都知道公司网络管理员有能力看到流量去向，但如此直观的数据呈现在眼前，还是难免让人背后一凉。笔者自己也警醒了一下，毕竟谁还没在工作间隙“摸过鱼”呢？不过转念一想，仅凭IP地址，公司大概率无法直接对应到具体个人（除非做了MAC地址绑定等额外配置），但这无疑是一个强烈的信号：在公司的网络环境下，你的“数字足迹”几乎是透明的。

评论区更是大型“人间真实”现场，充满了程序员的调侃与自省：

有网友指出，公司网络可以通过安装证书等方式进行深度包检测，隐私基本无从谈起；也有网友表示，这就是常规的“行为管理”；更有甚者，听说有公司开始以连接WiFi的时间来统计工时了。无论技术细节如何，这都提醒我们，对于网络安全和隐私保护需要多一份警惕。

话题从略显沉重的职场监控跳转一下，作为一名开发者，保持对数据结构和算法的敏锐同样重要。下面就来一起看看今天这道来自LeetCode的算法题——第1905题：统计子岛屿。

问题描述

给你两个 m x n 的二进制矩阵 grid1 和 grid2，它们只包含 0 （表示水域）和 1 （表示陆地）。一个岛屿 是由四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 中的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 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 区域是子岛屿，总共有 3 个子岛屿。

示例 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 区域是子岛屿，总共有 2 个子岛屿。

提示：

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1 <= m, n <= 500
• grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1。

解题思路

这道题要求我们计算 grid2 中有多少个岛屿是 grid1 中某个岛屿的子岛屿。关键在于理解“完全包含”的定义：grid2 中一个岛屿的所有陆地单元格，在 grid1 的相同位置上，必须都属于同一个岛屿。

一个直观的思路是两步走：

1. 为 grid1 中的岛屿编号：遍历 grid1，使用深度优先搜索（DFS）或广度优先搜索（BFS）找到所有连通区域（岛屿），并为每个岛屿赋予一个唯一的编号（例如从2开始，避免与原始的0、1冲突）。
2. 在 grid2 中寻找子岛屿：遍历 grid2，当遇到一块陆地（1）时，检查其在 grid1 中相同位置的值。
   • 如果 grid1 对应位置是水（0），那么 grid2 中以该位置为起点的整个岛屿都不可能是子岛屿。
   • 如果 grid1 对应位置是一个岛屿（编号>=2），则以此位置为起点，对 grid2 进行DFS/BFS，探索整个岛屿。在探索过程中，需要检查 grid2 岛屿的每一个陆地单元格，其在 grid1 中的编号是否都与起点位置在 grid1 中的编号完全相同。
   • 如果全部相同，则找到一个子岛屿；如果在探索过程中发现任何一处编号不同，则当前 grid2 的岛屿不是子岛屿。

代码实现

以下是使用DFS的Java和C++实现。

Java 版本：

private boolean isChild = true;// 是否是子岛屿

public int countSubIslands(int[][] grid1, int[][] grid2) {
    int m = grid1.length, n = grid1[0].length;
    int index = 2;// 给岛屿编号，相连的陆地是一个岛屿，他们的编号相同。
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid1[i][j] == 1)
                dfs1(grid1, i, j, index++);
        }
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 找到grid2的所有岛屿，且每个岛屿中每个位置都与岛屿1中该位置的岛屿编号相同,才算一个子岛屿
            if (grid2[i][j] == 1 && grid1[i][j] >= 2) {
                isChild = true;
                dfs2(grid2, i, j, grid1[i][j], grid1);
                if (isChild)
                    ans++;
            }
        }
    }
    return ans;
}

// 遍历矩阵1
private void dfs1(int[][] grid1, int i, int j, int index) {
    if (i < 0 || i >= grid1.length || j < 0 || j >= grid1[0].length || grid1[i][j] != 1)
        return;
    grid1[i][j] = index;// 挨着的陆地属于同一个岛屿
    dfs1(grid1, i - 1, j, index);// 上
    dfs1(grid1, i + 1, j, index);// 下
    dfs1(grid1, i, j - 1, index);// 左
    dfs1(grid1, i, j + 1, index);// 右
}

// 遍历矩阵2
private void dfs2(int[][] grid2, int i, int j, int index, int[][] grid1) {
    if (i < 0 || i >= grid2.length || j < 0 || j >= grid2[0].length || grid2[i][j] != 1)
        return;
    grid2[i][j] = -1;
    if (grid1[i][j] != index)
        isChild = false;// 不是子岛屿
    dfs2(grid2, i - 1, j, index, grid1);// 上
    dfs2(grid2, i + 1, j, index, grid1);// 下
    dfs2(grid2, i, j - 1, index, grid1);// 左
    dfs2(grid2, i, j + 1, index, grid1);// 右
}

C++ 版本：

public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid1.size();
        int n = grid1[0].size();
        int index = 2; // 给岛屿编号，相连的陆地是一个岛屿，他们的编号相同。
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid1[i][j] == 1)
                    dfs1(grid1, i, j, index++);
            }
        }

        int ans = 0;
        // 第二步：遍历 grid2，统计子岛屿数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 找到grid2的所有岛屿，且每个岛屿中每个位置都与岛屿1中该位置的岛屿编号相同,才算一个子岛屿
                if (grid2[i][j] == 1 && grid1[i][j] >= 2) {
                    isChild = true; // 重置标记
                    dfs2(grid2, i, j, grid1[i][j], grid1);
                    if (isChild)  // 如果是子岛屿，计数+1
                        ans++;
                }
            }
        }
        return ans;
    }

private:
    bool isChild = true;// 是否是子岛屿
    // 遍历矩阵1，给岛屿编号
    void dfs1(vector<vector<int>>& grid1, int i, int j, int index) {
        // 边界和合法性检查
        if (i < 0 || i >= grid1.size() || j < 0 || j >= grid1[0].size() || grid1[i][j] != 1)
            return;
        grid1[i][j] = index;// 挨着的陆地属于同一个岛屿// 挨着的陆地属于同一个岛屿
        // 上下左右递归遍历
        dfs1(grid1, i - 1, j, index); // 上
        dfs1(grid1, i + 1, j, index); // 下
        dfs1(grid1, i, j - 1, index); // 左
        dfs1(grid1, i, j + 1, index); // 右
    }

    // 遍历矩阵2，判断是否为子岛屿
    void dfs2(vector<vector<int>>& grid2, int i, int j, int index, vector<vector<int>>& grid1) {
        // 边界和合法性检查
        if (i < 0 || i >= grid2.size() || j < 0 || j >= grid2[0].size() || grid2[i][j] != 1)
            return;
        // 标记 grid2 ，避免重复遍历
        grid2[i][j] = -1;
        // 如果 grid1 对应位置的编号不一致，说明不是子岛屿
        if (grid1[i][j] != index)
            isChild = false;
        // 上下左右递归遍历
        dfs2(grid2, i - 1, j, index, grid1); // 上
        dfs2(grid2, i + 1, j, index, grid1); // 下
        dfs2(grid2, i, j - 1, index, grid1); // 左
        dfs2(grid2, i, j + 1, index, grid1); // 右
    }
};

总结

从警惕公司WiFi下的“数字裸奔”，到攻克一道关于岛屿包含关系的算法题，看似跳跃，实则都关乎“边界”与“规则”。前者是职场与隐私的边界，后者是算法中严谨的逻辑规则。作为开发者，我们既需要了解现实世界中的技术应用边界，保护自身权益，也需要持续锤炼解决复杂逻辑问题的能力。对这道题或者职场技术话题有更多想法？欢迎在云栈社区交流讨论。