# 130. Surrounded Regions

Given a 2D board containing `'X'` and `'O'` (**the letter O**), capture all regions surrounded by `'X'`.

A region is captured by flipping all `'O'`s into `'X'`s in that surrounded region.

**Example:**

```
X X X X
X O O X
X X O X
X O X X
```

After running your function, the board should be:

```
X X X X
X X X X
X X X X
X O X X
```

**Explanation:**

Surrounded regions shouldn’t be on the border, which means that any `'O'` on the border of the board are not flipped to `'X'`. Any `'O'` that is not on the border and it is not connected to an `'O'` on the border will be flipped to `'X'`. Two cells are connected if they are adjacent cells connected horizontally or vertically.

## Thoughts

由X和O组成的矩阵，将四周都被X围起来的O替换成X。UnionFind配合dummy node，把连在一起的结点像Number of Islands一样连起来，且把所有不被围着的（在边上的）和dummy node连起来。最后对每个'O'检查其是否和dummy node相连。

## Code

```python
class Solution:
    class UF:        
        def __init__(self, M, N):
            self.N = N
            self.parents = [0] * (M * N + 1)
            for i in range(len(self.parents)):
                self.parents[i] = i
            
        def un(self, r1, c1, r2, c2):
            x = self.find(r1 * self.N + c1 + 1)
            y = self.find(r2 * self.N + c2 + 1)
            self.parents[y] = x
            
        def find(self, x):
            while x != self.parents[x]:
                self.parents[x] = self.parents[self.parents[x]]
                x = self.parents[x]
            return x
        
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        M = len(board)
        N = len(board[0]) if M > 0 else 0
        uf = Solution.UF(M, N)
        cnt = 0
        for i in range(M):
            for j in range(N):
                if board[i][j] == 'X':
                    continue
                if i == 0 or i == M - 1 or j == 0 or j == N - 1:
                    uf.parents[i * N + j + 1] = 0
                if i - 1 >= 0 and board[i - 1][j] == 'O':
                    uf.un(i - 1, j, i, j)
                if j - 1 >= 0 and board[i][j - 1] == 'O':
                    uf.un(i, j - 1, i, j)
        z = uf.find(0)
        for i in range(M):
            for j in range(N):
                if board[i][j] == 'X':
                    continue
                x = uf.find(i * N + j + 1)
                if x == z:
                    continue
                board[i][j] = 'X'
    
```

```java
class Solution {
    class UnionFind {
        int[] fathers;
        int n;
        int count = 0;
        UnionFind(char[][] board) {
            int m = board.length;
            n = board[0].length;
            fathers = new int[m * n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        int id = i * n + j;
                        fathers[id] = id;
                        count++;   
                    }
                }
            }
            fathers[m * n] = m * n;
            count++;
        }

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

        public void union(int x1, int y1, int x2, int y2) {
            union(x1 * n + y1, x2 * n + y2);
        }

        public int find(int id) {
            if (id == fathers[id]) {
                return id;
            }
            fathers[id] = find(fathers[id]);
            return fathers[id];
        }

        public void union(int id1, int id2) {
            int find1 = find(id1);
            int find2 = find(id2);
            if (find1 != find2) {
                fathers[find1] = find2;
                count--;
            }
        }
    }


    public void solve(char[][] board) {
        if (board.length == 0) {
            return;
        }
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        UnionFind uf = new UnionFind(board);
        int n = board[0].length;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
                            if (board[x][y] == 'O') {
                                uf.union(i, j, x, y);
                            }
                        } else {
                            uf.union(i * n + j, board.length * n);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O' && !(uf.find(i, j) == uf.find(board.length * n))) {
                    board[i][j] = 'X';
                }
            }
        }

    }
}
```

## Analysis

时间复杂度不超过O(N^3), 空间复杂度O(N).


---

# Agent Instructions: 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/surrounded-regions.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.