> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/bing-cha-ji/130-bei-wei-rao-de-qu-yu.md).

# \[130]\[中等]\[并查集]\[DFS] 被围绕的区域

## 题目描述

[130. 被围绕的区域](https://leetcode-cn.com/problems/surrounded-regions/)

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

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

运行你的函数后，矩阵变为：

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

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

## 解题思路

### DFS

矩阵中有`X`和`O`两种字母, 但其实有三种元素:

* 字母 X
* 被字母 X 包围的字母 O
* 没有被字母 X 包围的字母 O

任何边界上的 O 都不会被填充为 X, 所有的不被包围的 O 都直接或间接与边界上的 O 相连, 我们可以利用这个性质判断 O 是否在边界上.

我们遍历所有边界位置, 从每一个的`O`开始, 搜索与之相连的`O`, 这些`O`最终都不会被置为`X`. 而剩余的`O`最终会被置为`X`. 因此在搜索过程中, 将边界上的`O`, 以及所有与之相连的`O`, 都临时置为`#`. 最后再统一的, 将矩阵中剩余的`O`置为`X`, 再将`#`恢复成`O`.

```python
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if n == 0:
            return board
        m = len(board[0])

        def dfs(i, j):
            if not 0 <= i < n or not 0 <= j < m:
                return
            if board[i][j] != 'O':
                return

            board[i][j] = '#'
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)
        for j in range(m):
            dfs(0, j)
            dfs(n - 1, j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == '#':
                    board[i][j] = 'O'
                elif board[i][j] == 'O':
                    board[i][j] = 'X'
```

### 并查集

并查集的思路也比较直观. 对于矩阵中的`O`, 我们将相连的`O`相连接, 组成一个集合. 而且, 我们知道不会被填充的`O`肯定是边界处的`O`或与之相连, 因此, 我们在为所有的`O`初始化集合编号时, **将所有边界上的`O`的祖先定义为同一个特殊的值**.

棋盘是二维的, 每个位置的祖先编号仍然是一个数值, 因此我们需要将每个**二维坐标映射到一维的唯一数字**, 常用的方法就是位置递增编号, 对于二维坐标`(x, y)`, 映射为`x * m + y`, 其中`m`是二维矩阵的列数. 这样共得到`0, 1, ..., m * n - 1`这些编号索引. 再加上上面说的**边界上的`O`的共同祖先**, 我们将其定义为`m * n`, 这种就得到了共`m * n + 1`个编号.

使用普通的并查集方法对齐进行查找合并, 最终遍历所有`O`的位置, 判断其最先是否为`m * n`, 对于不是的填充为`X`.

```python
class Union:
    def __init__(self, n):
        self.roots = list(range(n))

    def find(self, i):
        if self.roots[i] == i:
            return i
        self.roots[i] = self.find(self.roots[i])
        return self.roots[i]

    def union(self, a, b):
        self.roots[self.find(a)] = self.find(b)

    def connected(self, a, b):
        return self.find(a) == self.find(b)


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n = len(board)
        if n == 0:
            return board
        m = len(board[0])
        dummy = m * n

        u = Union(m * n + 1)

        for i in range(n):
            if board[i][0] == 'O':
                u.union(i * m, dummy)
            if board[i][m - 1] == 'O':
                u.union(i * m + m - 1, dummy)
        for j in range(m):
            if board[0][j] == 'O':
                u.union(j, dummy)
            if board[n - 1][j] == 'O':
                u.union((n - 1) * m + j, dummy)

        directs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    for row, col in directs:
                        if 0 <= i + row < n and 0 <= j + col < m and board[i + row][j + col] == 'O':
                            u.union((i + row) * m + j + col, i * m + j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O' and not u.connected(i * m + j, dummy):
                    board[i][j] = 'X'
```