Combined search /dfs solution - leetcode daily question - number of 1020 enclaves

Title Description

Topic link

title

One 、 Take the boundary value as the object to search and solve

At the beginning, I soon thought of using more violent direct dfs Deep search , And then it's over time .

Pay attention to this question because 1 Whether it can be extended to the whole border is valid by judging from outside 1 So we need to be clever , It should be based on all boundaries 1 For the object, first put all that can be exceeded 1 I found out , Then the rest 1 That's the answer .

Two 、 And look up the set and merge + Whether the border attribute is updated

Create a query set , Use a one-dimensional array to store all the elements of a two-dimensional array , At the same time, a one-dimensional array is added to determine whether the boundary is contiguous , Every time merge During the operation, it is necessary to judge whether the merge operation and the border update should be performed at the same time .

First use and search set merge be-all 1, Then judge whether it is contiguous one by one .

Solution code

dfs Method ：

class Solution {
    
public:
    vector<vector<int>> dirs = {
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};

    int numEnclaves(vector<vector<int>>& grid) {
    
        this->m = grid.size();
        this->n = grid[0].size();
        this->visited = vector<vector<bool>>(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
    
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
    
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }
        int enclaves = 0;
        for (int i = 1; i < m - 1; i++) {
    
            for (int j = 1; j < n - 1; j++) {
    
                if (grid[i][j] == 1 && !visited[i][j]) {
    
                    enclaves++;
                }
            }
        }
        return enclaves;
    }

    void dfs(const vector<vector<int>> & grid, int row, int col) {
    
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
    
            return;
        }
        visited[row][col] = true;
        for (auto & dir : dirs) {
    
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
private:
    int m, n;
    vector<vector<bool>> visited;
};

And look up the collection method ：

// This parallel search set is well written 
class UnionFind {
    
public:
    UnionFind(const vector<vector<int>> & grid) {
    
        int m = grid.size(), n = grid[0].size();
        this->parent = vector<int>(m * n);  // The connection relationship between storage and collection 
        this->onEdge = vector<bool>(m * n, false);// The key to finding whether there is a boundary element 
        this->rank = vector<int>(m * n);
        for (int i = 0; i < m; i++) {
       // Update and search the set according to the transmitted two-dimensional array , Simultaneous updating onEdge The boundary element is true
            for (int j = 0; j < n; j++) {
    
                if (grid[i][j] == 1) {
    
                    int index = i * n + j;
                    parent[index] = index;
                    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]) {
    // Here, it is treated as rank optimization 
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];// Each time the elements are merged, the relationship between this pile and the boundary is updated 
            } else if (rank[rootx] < rank[rooty]) {
    
                parent[rootx] = rooty;
                onEdge[rooty] = onEdge[rooty] | onEdge[rootx];
            } else {
    
                parent[rooty] = rootx;
                onEdge[rootx] = onEdge[rootx] | onEdge[rooty];
                rank[rootx]++;
            }
        }
    }

    bool isOnEdge(int i) {
    
        return onEdge[find(i)];
    }
private:
    vector<int> parent;  // And the necessary of search set 
    vector<bool> onEdge; // Judge whether it borders 
    vector<int> rank;    // By rank 
};

class Solution {
    
public:
    int numEnclaves(vector<vector<int>>& grid) {
    
        int m = grid.size(), n = grid[0].size();
        UnionFind uf(grid);
        // First of all 1 Connect , Then judge whether it borders 
        // Because the cycle is from top to bottom , From left to right , Therefore, the left and up directions do not need to be considered 
        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);
                    }
                }
            }
        }
        // Judge this 1 Whether it borders the border 
        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;
    }
};