130_被围绕的区域

难度：中等

题目

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

示例

示例一：

img

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

示例二：

输入：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
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
int row, col;

public void solve(char[][] board) {
  if (board == null || board.length == 0) return;
  row = board.length;
  col = board[0].length;
  for (int i = 0; i < row; i++) {
    dfs(board,i,0);
    dfs(board,i,col-1);
  }
  for (int i = 0; i < col; i++) {
    dfs(board,0,i);
    dfs(board,row-1,i);
  }
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < col; j++) {
      if (board[i][j] == 'O')
        board[i][j] = 'X';
      if (board[i][j] == '-')
        board[i][j] = 'O';
    }
  }
}

public void dfs(char[][] board, int i, int j) {
  if (i < 0 || j < 0 || i >= row || j >= col || 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);
}