# \[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'
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/bing-cha-ji/130-bei-wei-rao-de-qu-yu.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.