# 0130. 被围绕的区域

### 题目地址(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，并且题目明确说了边缘的所有 O 都是不可以变成 X 的。

![130.surrounded-regions](https://p.ipic.vip/6x2fc3.jpg)

其实我们观察会发现，我们除了边缘的 O 以及和边缘 O 连通的 O 是不需要变成 X 的，其他都要变成 X。

经过上面的思考，问题转化为连通区域问题。 这里我们需要标记一下`边缘的O以及和边缘O连通的O`。 我们当然可以用额外的空间去存，但是对于这道题目而言，我们完全可以 mutate。这样就空间复杂度会好一点。

整个过程如图所示：

> 我将`边缘的O以及和边缘O连通的O` 标记为了 "A"

![130.surrounded-regions](https://p.ipic.vip/qs9r9e.jpg)

### 关键点解析

* 二维数组 DFS 解题模板
* 转化问题为`连通区域问题`
* 直接 mutate 原数组，节省空间

### 代码

* 语言支持：JS，Python3, CPP

```js
/*
 * @lc app=leetcode id=130 lang=javascript
 *
 * [130] Surrounded Regions
 */
// 将O以及周边的O转化为A
function mark(board, i, j, rows, cols) {
  if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 || board[i][j] !== "O")
    return;

  board[i][j] = "A";
  mark(board, i + 1, j, rows, cols);
  mark(board, i - 1, j, rows, cols);
  mark(board, i, j + 1, rows, cols);
  mark(board, i, j - 1, rows, cols);
}
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  const rows = board.length;
  if (rows === 0) return [];
  const cols = board[0].length;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (i === 0 || i == rows - 1 || j === 0 || j === cols - 1) {
        mark(board, i, j, rows, cols);
      }
    }
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === "O") {
        board[i][j] = "X";
      } else if (board[i][j] === "A") {
        board[i][j] = "O";
      }
    }
  }

  return board;
};
```

Python Code：

```python
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 如果数组长或宽小于等于2，则不需要替换
        if len(board) <= 2 or len(board[0]) <= 2:
            return

        row, col = len(board), len(board[0])

        def dfs(i, j):
            """
            深度优先算法，如果符合条件，替换为A并进一步测试，否则停止
            """
            if i < 0 or j < 0 or i >= row or j >= col or board[i][j] != 'O':
                return
            board[i][j] = 'A'

            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        # 从外围开始
        for i in range(row):
            dfs(i, 0)
            dfs(i, col-1)

        for j in range(col):
            dfs(0, j)
            dfs(row-1, j)

        # 最后完成替换
        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'
```

CPP Code:

```cpp
class Solution {
    int M, N, dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    void dfs(vector<vector<char>> &board, int x, int y) {
        if (x < 0 || x >= M || y < 0 || y >= N || board[x][y] != 'O') return;
        board[x][y] = '#';
        for (auto &dir : dirs) dfs(board, x + dir[0], y + dir[1]);
    }
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        M = board.size(), N = board[0].size();
        for (int i = 0; i < M; ++i) {
            dfs(board, i, 0);
            dfs(board, i, N - 1);
        }
        for (int j = 0; j < N; ++j) {
            dfs(board, 0, j);
            dfs(board, M - 1, j);
        }
        for (auto &row : board) {
            for (auto &cell : row) {
                cell = cell == '#' ? 'O' : 'X';
            }
        }
    }
};
```

### 相关题目

* [200.number-of-islands](/leetcode-solution/medium/200.number-of-islands.md)

> 解题模板是一样的

**复杂度分析**

* 时间复杂度：$O(row \* col)$
* 空间复杂度：$O(row \* col)$

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/0cknrk.jpg)


---

# 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/130.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.