給定一個
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
TIP
反向思考：先從邊界的 ‘O’ 出發標記所有不會被包圍的 ‘O’，剩餘的 ‘O’ 就是被包圍的。
- 直接判斷哪些
'O'被包圍很難，反向思考更簡單 - 從四條邊界上的
'O'出發 DFS/BFS，將相連的'O'標記為安全（如改為'T'） - 遍歷整個 board：
'T'恢復為'O'，其餘'O'改為'X'
Approaches
1. BFS (from Border) — O(m * n) / O(m * n)
- Idea: 從邊界
'O'開始 BFS 標記安全區域，最後翻轉未標記的'O' - Time:
O(m * n) - Space:
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 (from Border) — O(m * n) / O(m * n)
- Idea: 從邊界
'O'遞迴 DFS 標記，程式碼更簡潔 - Time:
O(m * n) - Space:
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 同一思路
- Key trick: 用臨時標記
'T'區分「安全的 O」和「待翻轉的 O」，最後統一處理