LeetCode Surrounded Regions：邊緣 BFS 標記保留區域

題目描述

給定 m×n 矩陣 'X' 和 'O'，將所有被 'X' 完全包圍的 'O' 翻轉為 'X'。邊緣上的 'O' 及其連通區域不翻轉。

解法：反向思維 + BFS

1. 掃描四條邊緣，對每個 'O' 發起 BFS，標記所有連通 'O' 為「安全」（不翻轉）。
2. 掃描整個矩陣，未標記的 'O' 改為 'X'。

BFS 使用隊列，避免 DFS 棧溢出。關鍵優化：入隊時即標記，防止重複入隊導致指數級擴展（原文強調此點耗時 2 小時）。

參考代碼 (Java)

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0) return;
        int m = board.length, n = board[0].length;
        boolean[][] safe = new boolean[m][n];
        int[] dx = {-1,0,1,0}, dy = {0,1,0,-1};
        Queue q = new LinkedList<>();
        
        // 邊緣入隊
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') { q.add(new int[]{i,0}); safe[i][0]=true; }
            if (board[i][n-1] == 'O') { q.add(new int[]{i,n-1}); safe[i][n-1]=true; }
        }
        for (int j = 1; j < n-1; ++j) {
            if (board[0][j] == 'O') { q.add(new int[]{0,j}); safe[0][j]=true; }
            if (board[m-1][j] == 'O') { q.add(new int[]{m-1,j}); safe[m-1][j]=true; }
        }
        
        // BFS
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx<0 || nx>=m || ny<0 || ny>=n) continue;
                if (safe[nx][ny] || board[nx][ny] != 'O') continue;
                safe[nx][ny] = true; // 關鍵：入隊即標記
                q.add(new int[]{nx, ny});
            }
        }
        
        // 翻轉
        for (int i = 1; i < m-1; ++i)
            for (int j = 1; j < n-1; ++j)
                if (board[i][j] == 'O' && !safe[i][j])
                    board[i][j] = 'X';
    }
}

複雜度

• 時間：O(mn)，每個格子進隊出隊常數次。
• 空間：O(mn) 安全標記數組 + 隊列。