Surrounded Regions

130. 被围绕的区域

分析

标记无法被包围的区域：
- 从矩阵的边界出发，对边界的 ‘O’ 及其连通区域用 ‘*’ 标记，表示这些 ‘O’ 无法被包围。
填充被围绕的区域：
- 遍历矩阵，将未被标记的 ‘O’ 替换为 ‘X’，表示这些区域已被包围。
还原未被包围的区域：
- 将标记为 ‘*’ 的位置还原为 ‘O’。

时间复杂度

总时间复杂度 O(n * m)

空间复杂度

DFS 的递归调用栈深度与矩阵中最长的连通区域有关，空间复杂度为 O(n * m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


class Solution
{
public:
    int n = 0, m = 0; // 矩阵的行数和列数
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // 四个方向：右、下、左、上

    void solve(vector<vector<char>>& board)
    {
        n = board.size(), m = board[0].size();
        if (n == 0 || m == 0)
            return;

        // 从边界出发，标记无法被包围的区域
        for (int i = 0; i < n; ++i)
        {
            if (board[i][0] == 'O')
                dfs(board, i, 0); // 左边界
            if (board[i][m - 1] == 'O')
                dfs(board, i, m - 1); // 右边界
        }
        for (int i = 0; i < m; ++i)
        {
            if (board[0][i] == 'O')
                dfs(board, 0, i); // 上边界
            if (board[n - 1][i] == 'O')
                dfs(board, n - 1, i); // 下边界
        }

        // 遍历矩阵，处理未被标记的区域
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (board[i][j] == '*')
                    board[i][j] = 'O'; // 还原被标记的区域
                else
                    board[i][j] = 'X'; // 填充被包围的区域
            }
        }
    }

    void dfs(std::vector<std::vector<char>>& board, int x, int y)
    {
        board[x][y] = '*'; // 标记当前区域
        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i]; // 计算相邻位置
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O')
                dfs(board, a, b); // 递归标记连通区域
        }
    }
};