130. 被圍繞的區域

給你一個 m x n 的矩陣 board ，由若干字符 'X' 和 'O' 組成，捕獲 所有 被圍繞的區域：

  • 連接：一個單元格與水平或垂直方向上相鄰的單元格連接。
  • 區域：連接所有 'O' 的單元格來形成一個區域。
  • 圍繞：如果您可以用 'X' 單元格 連接這個區域，並且區域中沒有任何單元格位於 board 邊緣，則該區域被 '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']]

解釋：

130. 被圍繞的區域_i++





在上圖中，底部的區域沒有被捕獲，因為它在 board 的邊緣並且不能被圍繞。

示例 2：

輸入：board = [['X']]

輸出：[['X']]

 

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 為 'X' 或 'O'
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;

        // 1. 從邊界所有為 'O' 的格子出發，標記為 'S'（safe）
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') dfsMark(board, i, 0);
            if (board[i][n-1] == 'O') dfsMark(board, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfsMark(board, 0, j);
            if (board[m-1][j] == 'O') dfsMark(board, m-1, j);
        }

        // 2. 翻轉：未標記的 'O' -> 'X'（被包圍），標記的 'S' -> 'O'（恢復）
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'S') board[i][j] = 'O';
            }
        }
    }

    private void dfsMark(char[][] board, int i, int j) {
        int m = board.length, n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) return;
        if (board[i][j] != 'O') return;

        board[i][j] = 'S'; // 標記為 safe
        dfsMark(board, i + 1, j);
        dfsMark(board, i - 1, j);
        dfsMark(board, i, j + 1);
        dfsMark(board, i, j - 1);
    }
}
/*
1. Use DFS (or BFS). Time complexity is O(m·n).
2. A region should remain if and only if it connects to the border.
3. So start from the border: run DFS/BFS from every border cell that is 'O' and mark all reachable 'O' as safe.
4. After that pass, flip every unmarked 'O' to 'X', and restore the marked safe cells back to 'O'.  (flip remaining O → X and 'S' → O.)
*/