130. 被围绕的区域

✨核心逻辑

本题采用 边界搜索（DFS）+ 标记法 的策略：

边界不可围：根据题目规则，与矩阵边界相连的 'O' 是无法被 'X' 包围的，必须保留。
从边界向内搜索：遍历矩阵的四个边界（上下左右四条边）。一旦发现边界上的位置是 'O'，就以此位置为起点，触发深度优先搜索（DFS）。
特殊标记：在 DFS 的过程中，将与边界 'O' 相连的所有 'O' 统一修改为一个特殊标记字符（例如代码中的 'f'，代表“安全”或“标记”）。
最终转换：
- 再次遍历整个矩阵。凡是现在还是 'O' 的位置，说明它在内部且被 'X' 完全包围，将其修改为 'X'。
- 凡是标记为 'f' 的位置，说明它与边界相连是安全的，将其还原为 'O'。

🔥代码实现（含详细变量注释）

class Solution {
    public void solve(char[][] board) {
        // 边界情况判断：如果矩阵为空，直接结束方法
        if (board == null || board.length == 0) {
            return;
        }
        // m：记录矩阵的总行数
        int m = board.length;
        // n：记录矩阵的总列数
        int n = board[0].length;
        
        // 1. 遍历矩阵的四周外围，寻找边界上的 'O' 并向内深入 DFS
        // 遍历第一行和最后一行的每一列
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                dfs(board, m - 1, i);
            }
        }
        // 遍历第一列和最后一列的每一行
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        
        // 2. 统一处理内部矩阵，根据标记进行最终的覆盖还原
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果遍历到的字符依然是 'O'，说明它被 'X' 围绕，没有与边界相连，需要被替换为 'X'
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                // 如果遍历到的字符是之前标记的 'f'，说明它安全连接边界，将其还原为 'O'
                if (board[i][j] == 'f') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    // 辅助函数：深度优先搜索
    void dfs(char[][] board, int i, int j) {
        // 终止条件：如果越界（i 或 j 超出矩阵范围），或者当前格子不是 'O'
        // 注意这里判断条件是 board[i][j] != 'O'，它既阻止了对 'X' 的访问，也防止了对已经标记过的 'f' 重复访问
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        
        // 将当前安全的 'O' 标记为特殊字符 'f'，防止死循环，也方便后续区分
        board[i][j] = 'f';
        
        // 沿上下左右四个方向继续递归搜索
        dfs(board, i - 1, j); // 向上
        dfs(board, i + 1, j); // 向下
        dfs(board, i, j - 1); // 向左
        dfs(board, i, j + 1); // 向右
    }
}

⏱️复杂度分析
- 时间复杂度：O(M * N)，其中 M 是矩阵的行数，N 是矩阵的列数。外围的四个 for 循环和最后的双重 for 循环都只对矩阵元素进行线性遍历。DFS 过程中每个单元格最多被访问一次，总体操作次数与矩阵元素总数成正比。
- 空间复杂度：O(M * N)，主要消耗在 DFS 递归调用时系统隐式维护的栈空间。最坏情况下，整个矩阵全是由边界延伸出去的 'O'，递归深度可以达到矩阵元素的总数 M * N。