> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/union-find/number-of-enclaves.md).

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/union-find/number-of-enclaves.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.