# Number of Enclaves

<https://leetcode.com/contest/weekly-contest-130/problems/number-of-enclaves/>

> Given a 2D array`A`, each cell is 0 (representing sea) or 1 (representing land)
>
> A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
>
> Return the number of land squares in the grid for which we**cannot**walk off the boundary of the grid in any number of moves.
>
> **Example 1:**
>
> ```
> Input: 
> [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
> Output: 
> 3
> Explanation: 
>
> There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
> ```
>
> **Example 2:**
>
> ```
> Input: 
> [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
> Output: 
> 0
> Explanation: 
>
> All 1s are either on the boundary or can reach the boundary
> ```

## Solution

每个相连组成的1的块是一个集合，也就是看集合中有没有在边界的。有关“构成集合”的题无非UF和DFS。

```
class Solution {
public:
    int numEnclaves(vector<vector<int>>& A) {
        vector<pair<int, int>> dirs = {{0, 1}, {1, 0}};
        int m = A.size(), n = A[0].size();
        for (int i = 0; i < m * n; ++i) parents.push_back(i);
        set<int> bos;
        int total = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (A[i][j] == 1) {
                    int ind = i * n + j;
                    ++total;
                    if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                        bos.insert(ind);
                    }
                    for (const auto dir : dirs) {
                        int x = i + dir.first;
                        int y = j + dir.second;
                        if (x >= 0 && x < m && y >= 0 && y < n && A[x][y] == 1) {
                            un(x * n + y, ind);
                        }
                    }
                }
            }
        }

        for (int b : bos) {
            bos.insert(find(b));
        }

        for (int p : parents) {
            if (bos.find(find(p)) != bos.end()) --total;
        }
        return total;
    }

private:
    vector<int> parents;

    int td21d(int x, int y, int n) {
        return x * n + y;
    }

    int find(int x) {
        if (x != parents[x]) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }

    void un(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            parents[x] = y;
        }
    }
};
```