130. Surrounded Regions

Medium

Description

給定一個 m x n 的矩陣 board，包含 'X' 和 'O'。將所有被 'X' 完全包圍的 'O' 區域翻轉為 'X'。邊界上的 'O' 以及與邊界 'O' 相連的不算被包圍。

Example:

Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]] Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]

Intuition#

反向思考：先從邊界的 ‘O’ 出發標記所有不會被包圍的 ‘O’，剩餘的 ‘O’ 就是被包圍的。

直接判斷哪些 'O' 被包圍很難，反向思考更簡單
從四條邊界上的 'O' 出發 DFS/BFS，將相連的 'O' 標記為安全（如改為 'T'）
遍歷整個 board：'T' 恢復為 'O'，其餘 'O' 改為 'X'

Approaches#

1: BFS（從邊界出發）#

概念: 從邊界 'O' 開始 BFS 標記安全區域，最後翻轉未標記的 'O'
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun solve(board: Array<CharArray>) {
        val m = board.size
        val n = board[0].size
        val queue: ArrayDeque<Int> = ArrayDeque()
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        fun enqueue(i: Int, j: Int) {
            if (board[i][j] == 'O') {
                board[i][j] = 'T'
                queue.add(i * n + j)
            }
        }

        for (i in 0 until m) { enqueue(i, 0); enqueue(i, n - 1) }
        for (j in 0 until n) { enqueue(0, j); enqueue(m - 1, j) }

        while (queue.isNotEmpty()) {
            val cur = queue.removeFirst()
            val r = cur / n
            val c = cur % n
            for (d in 0 until 4) {
                val nr = r + dirs[d]
                val nc = c + dirs[d + 1]
                if (nr in 0 until m && nc in 0 until n && board[nr][nc] == 'O') {
                    board[nr][nc] = 'T'
                    queue.add(nr * n + nc)
                }
            }
        }

        for (i in 0 until m) {
            for (j in 0 until n) {
                board[i][j] = if (board[i][j] == 'T') 'O' else 'X'
            }
        }
    }
}

⭐2: DFS（從邊界出發）#

概念: 從邊界 'O' 遞迴 DFS 標記，程式碼更簡潔
時間複雜度: O(m * n)
空間複雜度: O(m * n)（遞迴堆疊）

class Solution {
    fun solve(board: Array<CharArray>) {
        val m = board.size
        val n = board[0].size

        fun dfs(i: Int, j: Int) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return
            board[i][j] = 'T'
            dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1)
        }

        for (i in 0 until m) { dfs(i, 0); dfs(i, n - 1) }
        for (j in 0 until n) { dfs(0, j); dfs(m - 1, j) }

        for (i in 0 until m) {
            for (j in 0 until n) {
                board[i][j] = if (board[i][j] == 'T') 'O' else 'X'
            }
        }
    }
}

🔑 Takeaways#

Pattern: 邊界反向搜尋 – 與 417. Pacific Atlantic Water Flow 同一思路
關鍵技巧: 用臨時標記 'T' 區分「安全的 O」和「待翻轉的 O」，最後統一處理