⭐ 题目日期：

阿里 - 2024/11/12

🌳 题目描述：

岛屿问题，被 X 包住的 O 全部改成 X

示例 1:
输入：
board = new char[][]{
    {'X', 'X', 'X', 'X'},
    {'X', 'O', 'O', 'X'},
    {'X', 'X', 'O', 'X'},
    {'X', 'O', 'X', 'X'}
};

输出：
board = new char[][]{
    {'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X'},
    {'X', 'X', 'X', 'X'},
    {'X', 'O', 'X', 'X'}
};

🕵🏽 面试评估：

这道题主要考查深度优先与广度优先遍历，中等偏上难度。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

O 有两种分布：1. 被 X 包围；2. 在边界或者找到一条全是 O 的路径到边界，这些 O 都没有被 X 包围

找到一个没有被 X 包围的 O 比找到一个被 X 包围的 O 更容易，因为所有边界的 O 都没有被 X 包围。 如果我们找到所有没有被 X 包围的 O，剩下的 O 全被 X 包围，将其改成 X 即可。

从所有的边界 O 进行深度优先遍历，标记能遍历到的所有 O，剩下没有遍历到的 O 为被 X 包围的。

💻代码：

Java

private int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

public void replaceSurroundedO(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) {
        return;
    }

    int rows = board.length;
    int cols = board[0].length;

    // 通过 DFS 标记与边界及与边界相连的 O
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                dfs(board, i, j);
            }
        }
    }

    // 执行完 DFS 后，将所有未标记的 O 替换为 X，标记过的 O 恢复为 O
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; 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 rows = board.length;
    int cols = board[0].length;
    if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') {
        return;
    }

    // 标记已经遍历过的 O，与常用的 isVisited = true; 逻辑相似，避免重复访问
    board[i][j] = '*';

    for (int[] direction : directions) {
        dfs(board, i + direction[0], j + direction[1]);
    }
}

🚵🏻复杂度分析：

假设矩阵 m 行 n 列

时间复杂度: O(mn), 矩阵被遍历两遍，矩阵中元素的个数为 m * n, 故时间复杂度为 O(mn)

空间复杂度: O(mn), 本题所用的解法没有额外引入空间标记访问过的没被 X 包围过的 O，采用原地改特殊值标记，空间复杂度来自递归栈的调用，递归栈调用的最大的深度为矩阵中元素的个数，最坏情况，所有的元素都为 O。

❗ 注意：

面试中，要与面试官沟通，能不能修改原矩阵，如果不能需引入额外相同大小的矩阵来标记。