Leetcode learning - day 36

Day 36

I use C++, Sorry for the mistake , The original intention of this article is only to urge me to study , If it happens to help you , I will be very happy .

One 、1254. Count the number of closed Islands

Two dimensional matrix grid from 0 （ land ） and 1 （ water ） form . The island is made up of the largest 4 Connected in two directions 0 Group composed of , The closed island is a Completely from 1 Surround （ Left 、 On 、 Right 、 Next ） The island of .

Please return Close the island Number of .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/number-of-closed-islands
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

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){
    // Traversing to the boundary indicates that it is not enclosed 
            return false;
        }
        if (grid[i][j] != 0){
    // Indicates being surrounded 
            return true;
        }
        grid[i][j] = 1;// Avoid repeated traversal 
        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;// Here we need to traverse step by step , Direct merger return If the first step is to act false You will not perform the following steps , It will cause subsequent setting 1 There is no place for 1, Will repeatedly increase the number of Islands 
    }
    int closedIsland(vector<vector<int>>& grid) {
    
        // It is very similar to the previous question , from 1 Surrounded by 0 It belongs to enclosed area , There are connected to the boundary 0 It belongs to an area that is not enclosed , About to be with the boundary 0 Connected 0 become 1, Then the rest 0 It's a closed area 
        // Or right 0 Depth-first traversal , Find the quilt 1 The surrounding area 
        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)){
    // To traverse the 
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Two 、1020. The number of enclaves

Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell .

once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the .

Return to grid unable The number of land cells that leave the grid boundary in any number of moves .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/number-of-enclaves
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Learn how to search sets

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;
    }
};

Tell the truth , I don't understand much ; Then take a closer look

3、 ... and 、1905. Statistical sub Islands

Here are two for you m x n The binary matrix of grid1 and grid2 , They only contain 0 （ Water area ） and 1 （ Representing land ）. One Islands By Four directions （ Horizontal or vertical ） On the adjacent 1 The composition of the region . Any area outside the matrix is considered a water area .

If grid2 An island of , By grid1 An island of Completely contain , in other words grid2 Every grid in the island is grid1 The same island in the world completely contains , Then we call grid2 This island in China is Sub Islands .

Please return grid2 in Sub Islands Of number .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/count-sub-islands
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .、

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){
    // Worth learning 
            queue<pair<int, int>> q;
            q.emplace(sx, sy);
            grid2[sx][sy] = 0;
            // The next step for judgment includes sx, sy Are all the islands at this point grid1 in 
            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;// Avoid repeated traversal 
                        if (grid1[nx][ny] != 1){
    // As long as one does not contain , Just 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;
    }
};