130. 被围绕的区域

1. 题目

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

示例 1：

img

1
2
3
输入：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：

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

提示：

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

2. 思路

  • 已知题目要求将被X围绕的区域中的O统一转换为X，同时已知题目中共存在以下三种元素：

    • 字母X
    • 被字母X围绕的字母O
    • 未被围绕的字母O

  • 根据题目特性，可以得知要达到无法转换字母O的条件，仅存在于关联到了边界的字母O的区域可以避免被围绕

  • 基于以上特性，可以将边界关联到的字母O区域统一转换为-符号，关联转换的过程采用DFS深度优先进行

  • 完成所有边界关联转化后，字母矩阵中剩余的字符O即为需要转化为X的单元格，随即对剩下的字母O进行统一转化

  • 而面对矩阵中剩下的字符-单元格，则是不需要转化的字母O，将其恢复为字母O

3. 代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private int totalRow;
    private int totalCol;


    public void solve(char[][] board) {
        totalRow = board.length;
        totalCol = board[0].length;

        for (var row = 0; row < totalRow; ++row) {
            markNoNeedReverse(board, row, 0);
            markNoNeedReverse(board, row, totalCol - 1);
        }

        for (var col = 1; col < totalCol; ++col) {
            markNoNeedReverse(board, 0, col);
            markNoNeedReverse(board, totalRow - 1, col);   
        }

        for (var row = 0; row < totalRow; ++row) {
            for (var col = 0; col < totalCol; ++col) {
                if (board[row][col] == 'O') {
                    board[row][col] = 'X';
                } else if (board[row][col] == '-') {
                    board[row][col] = 'O';
                }
            }
        }
    }

    private void markNoNeedReverse(char[][] board, int row, int col) {
        if (!isValidIndex(row, col) || board[row][col] != 'O') {
            return;
        }

        board[row][col] = '-';

        for(var i = 0; i < 4; ++i) {
            var direction = DIRECTIONS[i];
            var x = row + direction[0];
            var y = col + direction[1];

            markNoNeedReverse(board, x, y);
        }
    }

    private boolean isValidIndex(int row, int col) {
        return row >= 0 && row < totalRow && col >= 0 && col < totalCol;
    }
}

4. 复杂度

  • 时间复杂度：O(n * m)
  • 空间复杂度：O(n * m)

image-20231116215536674