LeetCode Surrounded Regions：DFS/BFS 邊界連通區域標記

問題描述

給定二維矩陣包含 'X' 和 'O'，將所有被 'X' 包圍的 'O' 翻轉為 'X'。邊界上的 'O' 及其連通的 'O' 不會被翻轉。

解法一：DFS（遞歸，可能棧溢出）

從四條邊界出發，遇到 'O' 進行 DFS，標記為臨時字符（如 'K'）。最後遍歷矩陣：'K' 改回 'O'，其餘 'O' 改為 'X'。遞歸深度可能超過棧限制。

解法二：BFS（隊列，推薦）

同理，但用隊列實現非遞歸遍歷，避免棧溢出。從邊界 'O' 入隊，四方向擴展標記 'K'。時間 O(mn)，空間 O(mn) 隊列最壞情況。

代碼實現 (Java BFS)

class Solution {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        if (m < 2 || n < 2) return;
        Deque q = new ArrayDeque<>();
        // 上下邊界
        for (int j = 0; j < n; ++j) {
            if (board[0][j] == 'O') { board[0][j] = 'K'; q.add(new int[]{0,j}); }
            if (board[m-1][j] == 'O') { board[m-1][j] = 'K'; q.add(new int[]{m-1,j}); }
        }
        // 左右邊界
        for (int i = 1; i < m-1; ++i) {
            if (board[i][0] == 'O') { board[i][0] = 'K'; q.add(new int[]{i,0}); }
            if (board[i][n-1] == 'O') { board[i][n-1] = 'K'; q.add(new int[]{i,n-1}); }
        }
        // BFS
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int x = cur[0] + d[0], y = cur[1] + d[1];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    board[x][y] = 'K';
                    q.add(new int[]{x,y});
                }
            }
        }
        // 還原
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                board[i][j] = (board[i][j] == 'K') ? 'O' : 'X';
    }
}

複雜度分析

• 時間複雜度：O(mn)。
• 空間複雜度：O(mn) 隊列。

總結

反向思維：不直接找被包圍區域，而是找「不被包圍」的區域（連通邊界）。BFS 避免遞歸棧溢出，是工程上更穩健的選擇。