leetcode1020. Number of enclaves (medium)

Ideas ：dfs/bfs The template questions
Follow leetcode130. The surrounding area （ secondary ） similar
https://blog.csdn.net/zhangjiaji111/article/details/123668205

class Solution {
    
public:
    int flag[505][505] = {
    0};
    int xy[4][2] = {
    0, 1, 0, -1, 1, 0, -1, 0};
    void dfs(vector<vector<int>>& grid, int x, int y) {
    
        int n = grid.size(), m = grid[0].size();
        flag[x][y] = 1;
        for (int i = 0; i < 4; ++i) {
    
            int xx = x + xy[i][0];
            int yy = y + xy[i][1];
            if (xx < 0 || xx > n - 1 || yy < 0 || yy > m - 1) continue;
            if (grid[xx][yy] && !flag[xx][yy]) dfs(grid, xx, yy);
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
    
        int n = grid.size(), m = grid[0].size();
        for (int j = 0; j < m; ++j) {
    
            if (grid[0][j] && !flag[0][j]) dfs(grid, 0, j);
            if (grid[n - 1][j] && !flag[n - 1][j]) dfs(grid, n - 1, j);
        }
        for (int i = 1; i < n - 1; ++i) {
    
            if (grid[i][0] && !flag[i][0]) dfs(grid, i, 0);
            if (grid[i][m - 1] && !flag[i][m - 1]) dfs(grid, i, m - 1);
        }
        int ans = 0;
        
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < m; ++j) {
    
                if (grid[i][j] && !flag[i][j]) ans++;
            }
        }
        return ans;
    }
};

Train of thought three ： Union checking set
Specific ideas ： Set up a virtual land ：n*m, When initializing, the land on the edge is connected with this cell . Then put the... In the figure 1 Construct several connected components .
ans： Cell is 1 And with the n*m Of findfather() Equal number .

class Solution {
    
public:
    vector<int> father;
    void unite (int u, int v) {
    
        int fau = findfather(u);
        int fav = findfather(v);
        if (fau != fav) father[fau] = fav;
    }
    int findfather(int m) {
    
        if (father[m] == m) return m;
        return father[m] = findfather(father[m]);
    }
    int numEnclaves(vector<vector<int>>& grid) {
    
 
        int n = grid.size(), m = grid[0].size();
        father.resize(n * m + 1);
        for (int i = 0; i < m * n + 1; ++i) {
    
            father[i] = i;
        }
        auto getindex = [&](int x, int y) {
    
            return x * m + y;
        };
        for (int j = 0; j < m; ++j) {
    
            if (grid[0][j]) unite(getindex(0, j), n * m);
            if (grid[n - 1][j]) unite(getindex(n - 1, j), n * m);
        }
        for (int i = 1; i < n - 1; ++i) {
    
            if (grid[i][0]) unite(getindex(i, 0), n * m);
            if (grid[i][m - 1]) unite(getindex(i, m - 1), n * m);
        }
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < m; ++j) {
    
                if (grid[i][j]) {
    
                    if (i - 1 >= 0 && grid[i - 1][j]) unite(getindex(i - 1, j), getindex(i, j));
                    if (j - 1 >= 0 && grid[i][j - 1]) unite(getindex(i, j - 1), getindex(i, j));
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < m; ++j) {
    
                if (grid[i][j] && findfather(getindex(i, j)) != findfather(n * m)) ans++;
            }
        }
        return ans;
    }
};