TNotes.leetcode

Appearance

⏰0130. 被围绕的区域【中等】

0130. 被围绕的区域【中等】 ​

1. 📝 题目描述 ​

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

  • 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
  • 区域：连接所有'O' 的单元格来形成一个区域。
  • 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。

通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。

示例 1：

txt
输入：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']]
  • 解释：
    • img
    • 在上图中，底部的区域没有被捕获，因为它在 board 的边缘并且不能被围绕。

示例 2：

txt
输入：board = [['X']]
输出：[['X']]

提示：

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

2. 🎯 s.1 - DFS 从边界出发 ​

c
void dfs(char** board, int m, int n, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
    board[i][j] = '#';
    dfs(board, m, n, i + 1, j);
    dfs(board, m, n, i - 1, j);
    dfs(board, m, n, i, j + 1);
    dfs(board, m, n, i, j - 1);
}

void solve(char** board, int boardSize, int* boardColSize) {
    int m = boardSize, n = boardColSize[0];
    for (int i = 0; i < m; i++) {
        dfs(board, m, n, i, 0);
        dfs(board, m, n, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        dfs(board, m, n, 0, j);
        dfs(board, m, n, m - 1, j);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == '#') board[i][j] = 'O';
            else if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
}
js
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  const m = board.length,
    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] = '#'
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)
  }
  // 从边界的 O 开始 DFS 标记为 #
  for (let i = 0; i < m; i++) {
    dfs(i, 0)
    dfs(i, n - 1)
  }
  for (let j = 0; j < n; j++) {
    dfs(0, j)
    dfs(m - 1, j)
  }
  // 还原：# -> O，O -> X
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === '#') board[i][j] = 'O'
      else if (board[i][j] === 'O') board[i][j] = 'X'
    }
  }
}
py
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        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)
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(n):
            dfs(0, j)
            dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == '#':
                    board[i][j] = 'O'
                elif board[i][j] == 'O':
                    board[i][j] = 'X'
  • 时间复杂度：O(m×n)，其中 m 和 n 分别是矩阵的行数和列数
  • 空间复杂度：O(m×n)，最坏情况下递归栈的深度

算法思路：

  • 逆向思维：不直接找被围绕的区域，而是先找不被围绕的区域（与边界相连的 O）
  • 从矩阵的四条边界出发，对所有边界上的 O 进行 DFS，将连通的 O 标记为 #
  • 最后遍历矩阵：# 恢复为 O，剩余的 O 翻转为 X