Medium

题目描述

给你一个 m x n 的矩阵 board ，由字符 'X' 和 'O' 组成，捕获所有被围绕的区域：

  • 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域：连接所有 'O' 的单元格来形成一个区域。
  • 围绕：如果您可以用 'X' 填充区域，并且填充后不会有任何 'O' 与边界上的 'O' 相连，则称此区域被围绕。

要捕获被围绕的区域，请用 'X' 填充所有被围绕的区域中的所有 'O'。

示例 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'

解题思路

解题思路

这道题的核心思想是反向思考：与其找到被围绕的 ‘O’，不如找到不被围绕的 ‘O’，然后将剩余的 ‘O’ 都转换为 ‘X’。

关键观察：不被围绕的 ‘O’ 必须满足以下条件之一：

  1. 位于边界上
  2. 与边界上的 ‘O’ 连通

算法流程：

  1. 标记边界连通的 ‘O’：从四条边界开始，对每个边界上的 ‘O’ 进行 DFS/BFS，将所有与边界连通的 ‘O’ 标记为临时字符（如 ‘#’）
  2. 处理内部区域：遍历整个矩阵，将未被标记的 ‘O’（即被围绕的 ‘O’）改为 ‘X’
  3. 恢复边界连通的 ‘O’：将临时标记 ‘#’ 恢复为 ‘O’

多种解法：

  • DFS（推荐）：递归实现，代码简洁
  • BFS：使用队列，避免递归深度过大导致栈溢出
  • 并查集：将边界上的点作为根节点，统一管理连通性

时间复杂度为 O(m×n)，每个位置最多访问一次。DFS 解法在实际应用中表现最佳，代码简洁易懂。

代码实现

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        
        int m = board.size(), n = board[0].size();
        
        // 标记边界上的O及其连通的O
        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改为X，标记的#改回O
        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(), 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);
    }
};

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return
        
        m, n = len(board), len(board[0])
        
        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及其连通的O
        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改为X，标记的#改回O
        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'

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0 || board[0].Length == 0) return;
        
        int m = board.Length, n = board[0].Length;
        
        // 标记边界上的O及其连通的O
        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改为X，标记的#改回O
        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, 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);
    }
}

var solve = function(board) {
    if (!board || board.length === 0) return;
    
    const m = board.length;
    const n = board[0].length;
    
    function dfs(i, j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') {
            return;
        }
        
        board[i][j] = 'T';
        
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
    
    // Mark all 'O's connected to border as 'T'
    for (let i = 0; i < m; i++) {
        if (board[i][0] === 'O') dfs(i, 0);
        if (board[i][n - 1] === 'O') dfs(i, n - 1);
    }
    
    for (let j = 0; j < n; j++) {
        if (board[0][j] === 'O') dfs(0, j);
        if (board[m - 1][j] === 'O') dfs(m - 1, j);
    }
    
    // Convert remaining 'O's to 'X's and 'T's back to 'O's
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] === 'T') {
                board[i][j] = 'O';
            }
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)每个位置最多访问一次，m 和 n 分别为矩阵的行数和列数
空间复杂度O(m×n)最坏情况下递归深度为 m×n（当整个矩阵都是 ‘O’ 时）

相关题目