Question

130. 被围绕的区域

English Version

题目描述

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

 

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

我们可以从矩阵的边界开始，将矩阵边界上的每个 O 作为起始点，开始进行深度优先搜索。将搜索到的 O 全部替换成 .。

然后我们再遍历这个矩阵，对于每个位置：

• 如果是 .，则替换成 O；
• 否则如果是 O，则替换成 X。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

class Solution:
  def solve(self, board: List[List[str]]) -> None:
    def dfs(i: int, j: int):
      if not (0 <= i < m and 0 <= j < n and board[i][j] == "O"):
        return
      board[i][j] = "."
      for a, b in pairwise((-1, 0, 1, 0, -1)):
        dfs(i + a, j + b)

    m, n = len(board), len(board[0])
    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"

class Solution {
  private final int[] dirs = {-1, 0, 1, 0, -1};
  private char[][] board;
  private int m;
  private int n;

  public void solve(char[][] board) {
    m = board.length;
    n = board[0].length;
    this.board = board;
    for (int i = 0; i < m; ++i) {
      dfs(i, 0);
      dfs(i, n - 1);
    }
    for (int j = 0; j < n; ++j) {
      dfs(0, j);
      dfs(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';
        }
      }
    }
  }

  private void dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
      return;
    }
    board[i][j] = '.';
    for (int k = 0; k < 4; ++k) {
      dfs(i + dirs[k], j + dirs[k + 1]);
    }
  }
}

class Solution {
public:
  void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int)> dfs = [&](int i, int j) {
      if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
        return;
      }
      board[i][j] = '.';
      for (int k = 0; k < 4; ++k) {
        dfs(i + dirs[k], j + dirs[k + 1]);
      }
    };
    for (int i = 0; i < m; ++i) {
      dfs(i, 0);
      dfs(i, n - 1);
    }
    for (int j = 1; j < n - 1; ++j) {
      dfs(0, j);
      dfs(m - 1, j);
    }
    for (auto& row : board) {
      for (auto& c : row) {
        if (c == '.') {
          c = 'O';
        } else if (c == 'O') {
          c = 'X';
        }
      }
    }
  }
};

func solve(board [][]byte) {
  m, n := len(board), len(board[0])
  dirs := [5]int{-1, 0, 1, 0, -1}
  var dfs func(i, j int)
  dfs = func(i, j int) {
    if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' {
      return
    }
    board[i][j] = '.'
    for k := 0; k < 4; k++ {
      dfs(i+dirs[k], j+dirs[k+1])
    }
  }
  for i := 0; i < m; i++ {
    dfs(i, 0)
    dfs(i, n-1)
  }
  for j := 0; j < n; j++ {
    dfs(0, j)
    dfs(m-1, j)
  }
  for i, row := range board {
    for j, c := range row {
      if c == '.' {
        board[i][j] = 'O'
      } else if c == 'O' {
        board[i][j] = 'X'
      }
    }
  }
}

function solve(board: string[][]): void {
  const m = board.length;
  const n = board[0].length;
  const dirs: number[] = [-1, 0, 1, 0, -1];
  const dfs = (i: number, j: number): void => {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') {
      return;
    }
    board[i][j] = '.';
    for (let k = 0; k < 4; ++k) {
      dfs(i + dirs[k], j + dirs[k + 1]);
    }
  };
  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);
  }
  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';
      }
    }
  }
}

impl Solution {
  pub fn solve(board: &mut Vec<Vec<char>>) {
    let m = board.len();
    let n = board[0].len();
    let dirs = vec![-1, 0, 1, 0, -1];

    fn dfs(
      board: &mut Vec<Vec<char>>,
      i: usize,
      j: usize,
      dirs: &Vec<i32>,
      m: usize,
      n: usize
    ) {
      if i >= 0 && i < m && j >= 0 && j < n && board[i][j] == 'O' {
        board[i][j] = '.';
        for k in 0..4 {
          dfs(
            board,
            ((i as i32) + dirs[k]) as usize,
            ((j as i32) + dirs[k + 1]) as usize,
            dirs,
            m,
            n
          );
        }
      }
    }

    for i in 0..m {
      dfs(board, i, 0, &dirs, m, n);
      dfs(board, i, n - 1, &dirs, m, n);
    }
    for j in 0..n {
      dfs(board, 0, j, &dirs, m, n);
      dfs(board, m - 1, j, &dirs, m, n);
    }

    for i in 0..m {
      for j in 0..n {
        if board[i][j] == '.' {
          board[i][j] = 'O';
        } else if board[i][j] == 'O' {
          board[i][j] = 'X';
        }
      }
    }
  }
}

public class Solution {
  private readonly int[] dirs = {-1, 0, 1, 0, -1};
  private char[][] board;
  private int m;
  private int n;

  public void Solve(char[][] board) {
    m = board.Length;
    n = board[0].Length;
    this.board = board;

    for (int i = 0; i < m; ++i) {
      Dfs(i, 0);
      Dfs(i, n - 1);
    }
    for (int j = 0; j < n; ++j) {
      Dfs(0, j);
      Dfs(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';
        }
      }
    }
  }

  private void Dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
      return;
    }
    board[i][j] = '.';
    for (int k = 0; k < 4; ++k) {
      Dfs(i + dirs[k], j + dirs[k + 1]);
    }
  }
}

方法二：并查集

我们也可以使用并查集，将矩阵边界上的每个 O 与一个超级节点 $m \times n$ 相连，将矩阵中的每个 O 与其上下左右的 O 相连。

然后我们遍历这个矩阵，对于每个位置，如果是 O，并且其与超级节点不相连，则将其替换成 X。

时间复杂度 $O(m \times n \times \alpha(m \times n))$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数，$\alpha$ 是阿克曼函数的反函数。

class Solution:
  def solve(self, board: List[List[str]]) -> None:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    m, n = len(board), len(board[0])
    p = list(range(m * n + 1))
    for i in range(m):
      for j in range(n):
        if board[i][j] == "O":
          if i in (0, m - 1) or j in (0, n - 1):
            p[find(i * n + j)] = find(m * n)
          else:
            for a, b in pairwise((-1, 0, 1, 0, -1)):
              x, y = i + a, j + b
              if board[x][y] == "O":
                p[find(x * n + y)] = find(i * n + j)
    for i in range(m):
      for j in range(n):
        if board[i][j] == "O" and find(i * n + j) != find(m * n):
          board[i][j] = "X"

class Solution {
  private int[] p;

  public void solve(char[][] board) {
    int m = board.length;
    int n = board[0].length;
    p = new int[m * n + 1];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == 'O') {
          if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
            p[find(i * n + j)] = find(m * n);
          } else {
            for (int k = 0; k < 4; ++k) {
              int x = i + dirs[k];
              int y = j + dirs[k + 1];
              if (board[x][y] == 'O') {
                p[find(x * n + y)] = find(i * n + j);
              }
            }
          }
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == 'O' && find(i * n + j) != find(m * n)) {
          board[i][j] = 'X';
        }
      }
    }
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  void solve(vector<vector<char>>& board) {
    int m = board.size(), n = board[0].size();
    vector<int> p(m * n + 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find = [&](int x) {
      return p[x] == x ? x : p[x] = find(p[x]);
    };
    int dirs[5] = {-1, 0, 1, 0, -1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == 'O') {
          if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
            p[find(i * n + j)] = find(m * n);
          } else {
            for (int k = 0; k < 4; ++k) {
              int x = i + dirs[k];
              int y = j + dirs[k + 1];
              if (board[x][y] == 'O') {
                p[find(x * n + y)] = find(i * n + j);
              }
            }
          }
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == 'O' && find(i * n + j) != find(m * n)) {
          board[i][j] = 'X';
        }
      }
    }
  }
};

func solve(board [][]byte) {
  m, n := len(board), len(board[0])
  p := make([]int, m*n+1)
  for i := range p {
    p[i] = i
  }
  var find func(x int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  dirs := [5]int{-1, 0, 1, 0, -1}
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if board[i][j] == 'O' {
        if i == 0 || i == m-1 || j == 0 || j == n-1 {
          p[find(i*n+j)] = find(m * n)
        } else {
          for k := 0; k < 4; k++ {
            x, y := i+dirs[k], j+dirs[k+1]
            if board[x][y] == 'O' {
              p[find(x*n+y)] = find(i*n + j)
            }
          }
        }
      }
    }
  }
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if board[i][j] == 'O' && find(i*n+j) != find(m*n) {
        board[i][j] = 'X'
      }
    }
  }
}

function solve(board: string[][]): void {
  const m = board.length;
  const n = board[0].length;
  const p: number[] = Array(m * n + 1)
    .fill(0)
    .map((_, i) => i);
  const dirs: number[] = [-1, 0, 1, 0, -1];
  const find = (x: number): number => {
    if (p[x] !== x) {
      p[x] = find(p[x]);
    }
    return p[x];
  };
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (board[i][j] === 'O') {
        if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
          p[find(i * n + j)] = find(m * n);
        } else {
          for (let k = 0; k < 4; ++k) {
            const [x, y] = [i + dirs[k], j + dirs[k + 1]];
            if (board[x][y] === 'O') {
              p[find(x * n + y)] = find(i * n + j);
            }
          }
        }
      }
    }
  }
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (board[i][j] === 'O' && find(i * n + j) !== find(m * n)) {
        board[i][j] = 'X';
      }
    }
  }
}