LeetCode 第130题：被围绕的区域

题目描述

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：board = [["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'。如果两个元素在水平或垂直方向相邻，则称它们是"相连"的。

示例 2：

输入：board = [["X"]]
输出：[["X"]]

提示

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] 为 'X' 或 'O'

解题思路

方法一：深度优先搜索（DFS）

这道题的关键是找出所有不被 ‘X’ 围绕的 ‘O’，也就是与边界上的 ‘O’ 相连的 ‘O’。我们可以从边界上的每个 ‘O’ 开始，使用深度优先搜索（DFS）标记所有与之相连的 ‘O’，然后将剩余的 ‘O’（即被 ‘X’ 围绕的 ‘O’）替换为 ‘X’。

关键点：

从边界上的每个 ‘O’ 开始进行DFS
标记所有与边界上的 ‘O’ 相连的 ‘O’
将未被标记的 ‘O’ 替换为 ‘X’

具体步骤：

遍历矩阵的四条边界，对于每个边界上的 ‘O’，使用DFS标记所有与之相连的 ‘O’（可以将其标记为特殊字符，如 ‘#’）
遍历整个矩阵：
- 将所有标记为 ‘#’ 的单元格恢复为 ‘O’
- 将所有未被标记的 ‘O’ 替换为 ‘X’

时间复杂度：O(m * n)，其中m和n分别是矩阵的行数和列数，需要遍历整个矩阵。空间复杂度：O(m * n)，最坏情况下，矩阵中的所有单元格都是 ‘O’，递归调用栈的深度为m * n。

方法二：广度优先搜索（BFS）

我们也可以使用广度优先搜索（BFS）来解决这个问题。BFS使用队列来存储待访问的单元格。

关键点：

从边界上的每个 ‘O’ 开始进行BFS
使用队列存储待访问的单元格
标记所有与边界上的 ‘O’ 相连的 ‘O’

具体步骤：

遍历矩阵的四条边界，对于每个边界上的 ‘O’，将其加入队列，并标记为特殊字符（如 ‘#’）
进行BFS：
- 从队列中取出一个单元格
- 检查其上下左右四个相邻的单元格，如果是 ‘O’，则将其加入队列，并标记为 ‘#’
遍历整个矩阵：
- 将所有标记为 ‘#’ 的单元格恢复为 ‘O’
- 将所有未被标记的 ‘O’ 替换为 ‘X’

时间复杂度：O(m * n)，其中m和n分别是矩阵的行数和列数，需要遍历整个矩阵。空间复杂度：O(m * n)，最坏情况下，矩阵中的所有单元格都是 ‘O’，队列的大小为m * n。

方法三：并查集

并查集是一种树形的数据结构，用于处理一些不交集的合并及查询问题。我们可以使用并查集来解决这个问题。

关键点：

创建一个虚拟节点，表示边界外部
将所有边界上的 ‘O’ 与虚拟节点连接
将相邻的 ‘O’ 连接起来
检查每个 ‘O’ 是否与虚拟节点连接，如果不是，则将其替换为 ‘X’

具体步骤：

创建一个并查集，包含一个虚拟节点（表示边界外部）
遍历矩阵的四条边界，对于每个边界上的 ‘O’，将其与虚拟节点连接
遍历整个矩阵，对于每个 ‘O’，将其与相邻的 ‘O’ 连接
再次遍历整个矩阵，对于每个 ‘O’，检查其是否与虚拟节点连接，如果不是，则将其替换为 ‘X’

时间复杂度：O(m * n)，其中m和n分别是矩阵的行数和列数，需要遍历整个矩阵。空间复杂度：O(m * n)，需要存储并查集的数据结构。

图解思路

DFS过程分析表

以示例1为例：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]

步骤	操作	矩阵状态	说明
初始状态	-	[[“X”,“X”,“X”,“X”], [“X”,“O”,“O”,“X”], [“X”,“X”,“O”,“X”], [“X”,“O”,“X”,“X”]]	原始矩阵
步骤1	从边界上的’O’开始DFS	[[“X”,“X”,“X”,“X”], [“X”,“O”,“O”,“X”], [“X”,“X”,“O”,“X”], [“X”,“#”,“X”,“X”]]	标记与边界上的’O’相连的’O’为’#’
步骤2	将未标记的’O’替换为’X’	[[“X”,“X”,“X”,“X”], [“X”,“X”,“X”,“X”], [“X”,“X”,“X”,“X”], [“X”,“#”,“X”,“X”]]	将所有未标记的’O’替换为’X’
步骤3	将标记的’#‘恢复为’O’	[[“X”,“X”,“X”,“X”], [“X”,“X”,“X”,“X”], [“X”,“X”,“X”,“X”], [“X”,“O”,“X”,“X”]]	将所有标记的’#‘恢复为’O’

连通区域分析表

区域	位置	是否与边界相连	最终状态	说明
区域1	(1,1), (1,2), (2,2)	否	‘X’	被’X’围绕，需要替换为’X’
区域2	(3,1)	是	‘O’	与边界相连，保持为’O’

代码实现

C# 实现

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) {
            return;
        }
        
        int m = board.Length;
        int n = board[0].Length;
        
        // 从边界上的'O'开始DFS
        for (int i = 0; i < m; i++) {
            // 左边界
            if (board[i][0] == 'O') {
                DFS(board, i, 0);
            }
            // 右边界
            if (board[i][n - 1] == 'O') {
                DFS(board, i, n - 1);
            }
        }
        
        for (int j = 0; j < n; j++) {
            // 上边界
            if (board[0][j] == 'O') {
                DFS(board, 0, j);
            }
            // 下边界
            if (board[m - 1][j] == 'O') {
                DFS(board, m - 1, j);
            }
        }
        
        // 将标记的'#'恢复为'O'，将未标记的'O'替换为'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    private void DFS(char[][] board, int i, int j) {
        int m = board.Length;
        int n = board[0].Length;
        
        // 边界检查
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        
        // 标记当前单元格
        board[i][j] = '#';
        
        // 递归处理上下左右四个方向
        DFS(board, i - 1, j); // 上
        DFS(board, i + 1, j); // 下
        DFS(board, i, j - 1); // 左
        DFS(board, i, j + 1); // 右
    }
}

Python 实现

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        
        # DFS函数
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return
            
            # 标记当前单元格
            board[i][j] = '#'
            
            # 递归处理上下左右四个方向
            dfs(i - 1, j) # 上
            dfs(i + 1, j) # 下
            dfs(i, j - 1) # 左
            dfs(i, j + 1) # 右
        
        # 从边界上的'O'开始DFS
        for i in range(m):
            # 左边界
            if board[i][0] == 'O':
                dfs(i, 0)
            # 右边界
            if board[i][n - 1] == 'O':
                dfs(i, n - 1)
        
        for j in range(n):
            # 上边界
            if board[0][j] == 'O':
                dfs(0, j)
            # 下边界
            if board[m - 1][j] == 'O':
                dfs(m - 1, j)
        
        # 将标记的'#'恢复为'O'，将未标记的'O'替换为'X'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

C++ 实现

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) {
            return;
        }
        
        int m = board.size();
        int n = board[0].size();
        
        // 从边界上的'O'开始DFS
        for (int i = 0; i < m; i++) {
            // 左边界
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            // 右边界
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        
        for (int j = 0; j < n; j++) {
            // 上边界
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            // 下边界
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }
        
        // 将标记的'#'恢复为'O'，将未标记的'O'替换为'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
private:
    void dfs(vector<vector<char>>& board, int i, int j) {
        int m = board.size();
        int n = board[0].size();
        
        // 边界检查
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        
        // 标记当前单元格
        board[i][j] = '#';
        
        // 递归处理上下左右四个方向
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
};

执行结果

C# 实现

执行用时：108 ms
内存消耗：47.2 MB

Python 实现

执行用时：44 ms
内存消耗：18.6 MB

C++ 实现

执行用时：8 ms
内存消耗：10.1 MB

性能对比

语言	执行用时	内存消耗	特点
C#	108 ms	47.2 MB	执行速度适中，内存消耗较高
Python	44 ms	18.6 MB	执行速度适中，内存消耗适中
C++	8 ms	10.1 MB	执行速度最快，内存消耗最低

代码亮点

🎯 使用DFS从边界开始标记，思路清晰直观
💡 巧妙使用临时标记’#‘，避免混淆已处理和未处理的’O’
🔍 边界条件处理完善，包括空矩阵和边界检查
🎨 代码结构清晰，逻辑简单易懂

常见错误分析

🚫 没有正确处理边界上的’O’，导致结果错误
🚫 DFS实现不当，没有正确标记与边界相连的’O’
🚫 没有正确处理空矩阵的情况
🚫 递归深度过大，导致栈溢出

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS	O(m * n)	O(m * n)	实现简单，思路清晰	递归调用可能导致栈溢出
BFS	O(m * n)	O(m * n)	避免递归调用栈溢出	实现稍复杂，需要使用队列
并查集	O(m * n)	O(m * n)	适合处理连通性问题	实现复杂，不直观

题目描述

难度

题目链接

示例

示例 1：

示例 2：

提示

解题思路

方法一：深度优先搜索（DFS）

方法二：广度优先搜索（BFS）

方法三：并查集

图解思路

DFS过程分析表

连通区域分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目