> 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/surrounded-regions.md).

# 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).