leetcode1020. 飞地的数量（中等）

思路：dfs/bfs模板题
跟 leetcode130.被围绕的区域（中等） 类似
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;
    }
};

思路三：并查集
具体思路：设置一个虚拟的陆地：n*m，初始化时边缘的陆地与该单元格连通。然后将图中的1构造若干个连通分量。
ans：单元格为1且与n*m的findfather()相等的个数。

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