这以后谁还敢连公司Wifi。|dfs|grid|wifi|算法

最近在网上看到一张截图，一家公司通过网络统计了全公司平均工作占比，以及按时上线的准时率，还有工作期间大家都看了哪些网站，网友评论到以后谁还敢连接公司WiFi。

不过我知道公司是可以检测到你浏览了哪些网站，但我确实没注意，因为我经常在工作的时候没事也会看看招聘网站，以后我也要注意了。不过退一步来说就是看了，公司也不知道是谁看的，因为他不知道哪个连的是你的手机。这里也提醒大家工作时候尽量不要连公司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 。

问题分析

这题让计算右边的矩阵中有多少个岛屿是左边矩阵的子岛屿，所谓的岛屿，也就是连在一起的陆地，称为一个岛屿。所谓的子岛屿，也就是一个岛屿的所有陆地都被另一个岛屿包含。

解这题之前，我们先把左边矩阵中所有的岛屿都编上号，因为矩阵中只有 0 和 1 ，我们编号从 2 开始。由于这两个矩阵的长和宽都是一样的，我们遍历右边矩阵的时候，如果遇到一块陆地，然后再判断左边对应的位置是不是一个岛屿，如果左边对应的位置不是一个岛屿，那么右边和这块陆地相连的岛屿就不可能是左边的子岛屿。

如果左边对应的位置是一个岛屿，那么还要判断右边和该陆地相连的所有陆地（因为他们属于同一岛屿）是否都属于左边的那个岛屿。

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> &grid1, vector> &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> &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> &grid2, int i, int j, int index, vector> &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); // 右
    }