第三十六天

我使用的C++，错误的地方请见谅，文章初衷仅用来督促本人学习，如果恰巧能够给你带来帮助，我会十分开心。

文章目录

第三十六天
一、1254. 统计封闭岛屿的数目
二、1020. 飞地的数量
三、1905. 统计子岛屿

一、1254. 统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个完全由1包围（左、上、右、下）的岛。

请返回封闭岛屿的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-closed-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    bool dfs(vector<vector<int>>& grid, int i, int j, int n, int m){
        if (i < 0 || i >= n || j < 0 || j >= m){//遍历至边界则表示未被封闭
            return false;
        }
        if (grid[i][j] != 0){//表示被包围
            return true;
        }
        grid[i][j] = 1;//避免重复遍历
        bool b1 = dfs(grid, i + 1, j, n, m);
        bool b2 = dfs(grid, i - 1, j, n, m);
        bool b3 = dfs(grid, i, j + 1, n, m);
        bool b4 = dfs(grid, i, j - 1, n, m);
       /* return dfs(grid, i + 1, j, n, m) && dfs(grid, i - 1, j, n, m) && dfs(grid, i, j + 1, n, m) && dfs(grid, i, j - 1, n, m);*/
       return b1 && b2 && b3 && b4;//这里要分开一步一步遍历，直接合并return的话如果第一步执行为false就不会再执行后面的步骤，会导致后续该置1的地方没有置1，会重复增加岛屿数
    }
    int closedIsland(vector<vector<int>>& grid) {
        //和之前的一道题很像，由1包围的0属于封闭区域，有连接到边界的0则属于不被封闭的区域，即将与边界0相连的0变成1，之后其余的0就是封闭区域
        //或者对0深度优先遍历，找到被1包围的区域
        int n = grid.size(), m = grid[0].size(), ans = 0;
        
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                if (grid[i][j] == 0 && dfs(grid, i, j, n, m)){//开始遍历
                    ++ans;
                }
            }
        }
        return ans;
    }
};

二、1020. 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-enclaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
在这里插入图片描述

学习一下并查集的做法

class UF{
public:
    UF(const vector<vector<int>>& grid){
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);
        this->onEdge = vector<bool>(m * n, false);
        this->rank = vector<int>(m * n);
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (grid[i][j] == 1){
                    int index = i * n + j;
                    parent[index] = i * n + j;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1){
                        onEdge[index] = true;
                    }
                }
            }
        }
    }

    int find (int i){
        if (parent[i] != i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void uni(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty){
            if (rank[rootx] > rank[rooty]){
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
            }
            else if (rank[rootx] < rank[rooty]){
                parent[rootx] = rooty;
                onEdge[rooty] = onEdge[rootx] | onEdge[rooty];
            }
            else {
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
                ++rank[rootx];
            }
        }
    }

    bool isOnEdge(int i){
        return onEdge[find(i)];
    }
private:
    vector<int> parent;
    vector<bool> onEdge;
    vector<int> rank;
};

class Solution{
public:
    int numEnclaves(vector<vector<int>>& grid){
        int m = grid.size(), n = grid[0].size();
        UF uf(grid);
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (grid[i][j] == 1){
                    int index = i * n + j;
                    if (j + 1 < n && grid[i][j + 1] == 1){
                        uf.uni(index, index + 1);
                    }
                    if (i + 1 < m && grid[i + 1][j] == 1){
                        uf.uni(index, index + n);
                    }
                }
            }
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; ++i){
            for (int j = 1; j < n - 1; ++j){
                if (grid[i][j] == 1 && !uf.isOnEdge(i * n + j)){
                    ++enclaves;
                }
            }
        }
        return enclaves;
    }
};

说实话，没太看懂；之后要再仔细看看

三、1905. 统计子岛屿

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

如果 grid2 的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为子岛屿。

请你返回 grid2 中子岛屿的数目。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-sub-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。、

class Solution {
private:
    static constexpr array<array<int , 2>, 4> dirs = {{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}};
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m = grid1.size(), n = grid1[0].size();
        auto bfs = [&](int sx, int sy){//值得学习
            queue<pair<int, int>> q;
            q.emplace(sx, sy);
            grid2[sx][sy] = 0;
            //下一为判断包括sx, sy这个点的岛屿是否都在grid1中
            bool check = grid1[sx][sy];
            while (!q.empty()){
                auto [x, y] = q.front();
                q.pop();
                for (int k = 0; k < 4; ++k){
                    int nx = x + dirs[k][0];
                    int ny = y + dirs[k][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid2[nx][ny] == 1){
                        q.emplace(nx, ny);
                        grid2[nx][ny] = 0;//避免重复遍历
                        if (grid1[nx][ny] != 1){//只要有一个不包含，就false
                            check = false;
                        }
                    }
                }
            }
            return check;
        };
        int ans = 0;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (grid2[i][j] == 1){
                    ans += bfs(i, j);
                }
            }
        }
        return ans;
    }
};