Surrounded Regions: tại sao bạn giải ngược từ biên

Bài toán nghe như một trò chơi chiếm đất: một vùng ô 'O' bị bao quanh khi mọi ô trong vùng đó được khép kín bởi 'X' và không có ô nào chạm biên bảng. Thay thế các vùng bị bao quanh thành 'X', in-place.

Cách tấn công trực tiếp: duyệt mọi 'O', flood-fill vùng liên kết, kiểm tra xem có ô nào nằm trên biên không. Nếu không — capture toàn bộ vùng. Cách này đúng. Nhưng cũng có thể tốn O((m*n)^2) trong trường hợp xấu nhất, vì bảng toàn 'O' khiến mỗi điểm xuất phát đều phải duyệt toàn bộ ma trận trước khi kết luận vùng đó an toàn.

Có cách sạch hơn. Thay vì hỏi "vùng này có bị bao quanh không?" với từng 'O', hỏi câu bổ sung một lần: "ô 'O' nào có thể reach được từ biên?" Bất kỳ 'O' nào reach được từ biên đều không thể bị bao quanh — nó có đường thoát. Mọi 'O' còn lại đều bị capture. Chạy pass reachability đó một lần, đánh dấu các ô sống sót, rồi quét cuối cùng. Toàn bộ tốn O(m*n).

Sự đảo ngược đó — giải phần bổ sung, không phải bài gốc — là insight thiết kế mà bài này dạy.

Đề bài

Cho một ma trận m x n chỉ chứa ký tự 'X' và 'O', hãy capture tất cả các vùng 'O' bị bao quanh hoàn toàn bởi 'X' — tức là không có ô nào trong vùng đó chạm biên bảng — bằng cách thay thế các 'O' đó thành 'X' in-place. Full statement: LeetCode 130.

Ràng buộc:
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] là 'X' hoặc 'O'.

Constraints nói gì trước khi viết một dòng

Bảng là m x n với 1 <= m, n <= 200. Tối đa 40,000 ô. DFS hoặc BFS duyệt mỗi ô nhiều nhất một lần hoàn toàn phù hợp. Giải pháp O((m*n)^2) có thể lên đến 1.6 * 10^9 phép tính — về lý thuyết có thể chạy được với constant nhỏ, nhưng rủi ro và không cần thiết.

Ràng buộc board[i][j] chỉ là 'X' hoặc 'O' quan trọng cho trick đánh dấu. Ta có thể dùng ký tự thứ ba — source dùng '#' — làm marker tạm thời "an toàn" mà không lo xung đột. Alphabet hai ký tự có nghĩa là bất kỳ ký tự nào khác đều rõ ràng là của ta.

Stack overflow đáng lưu ý. Bảng 200x200 toàn 'O' có thể đẩy recursive DFS sâu đến 40,000 frame. Giới hạn recursion mặc định của Python là 1000. Approach DFS đệ quy hoạt động với hầu hết test case nhưng sẽ gặp lỗi recursion limit trên input cực đoan. BFS tránh điều này hoàn toàn vì queue sống trên heap.

Approach 1: brute-force DFS từng ô

Với mỗi 'O' chưa thăm, flood-fill vùng liên kết của nó, theo dõi xem có ô nào chạm biên không, rồi quyết định dựa trên kết quả.

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
 
        m, n = len(board), len(board[0])
 
        def dfs(i: int, j: int, region: list) -> bool:
            # Ngoài biên hoặc không phải 'O': OK, không chạm biên ở đây
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return True
 
            # Đang ở biên: vùng này không thể bị capture
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                return False
 
            board[i][j] = '#'   # đánh dấu đã thăm
            region.append((i, j))
 
            can_capture = True
            for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if not dfs(i + di, j + dj, region):
                    can_capture = False
 
            return can_capture
 
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    region: list = []
                    if dfs(i, j, region):
                        for x, y in region:
                            board[x][y] = 'X'
                    else:
                        for x, y in region:
                            board[x][y] = 'O'   # khôi phục

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0 || board[0].Length == 0) return;
 
        int m = board.Length, n = board[0].Length;
        var region = new System.Collections.Generic.List<(int, int)>();
 
        bool DFS(int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
                return true;
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
                return false;
 
            board[i][j] = '#';
            region.Add((i, j));
 
            bool canCapture = true;
            int[] di = { 0, 0, 1, -1 };
            int[] dj = { 1, -1, 0, 0 };
            for (int d = 0; d < 4; d++) {
                if (!DFS(i + di[d], j + dj[d]))
                    canCapture = false;
            }
            return canCapture;
        }
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    region.Clear();
                    if (DFS(i, j)) {
                        foreach (var (x, y) in region) board[x][y] = 'X';
                    } else {
                        foreach (var (x, y) in region) board[x][y] = 'O';
                    }
                }
            }
        }
    }
}

Nhược điểm tinh tế nhưng thực: khi DFS tìm thấy ô biên, nó trả về false — nhưng DFS đã đệ quy sâu vào trong vùng, đánh dấu nhiều ô là '#'. Tất cả các ô đó phải được khôi phục. Nếu vùng lớn và bảng có nhiều vùng như vậy, ta duyệt lại cùng ô nhiều lần. Time: O((m*n)^2). Space: O(m*n) cho call stack và danh sách region.

Approach 2: DFS từ biên — sự đảo ngược sạch sẽ

Lật câu hỏi. Bắt đầu từ mọi 'O' trên bốn biên. DFS từ mỗi ô, đánh dấu ô reach được là '#' (an toàn). Sau pass quét biên, mọi 'O' còn lại không reach được từ biên — nó bị bao quanh. Một pass cuối: 'O' -> 'X', '#' -> 'O'.

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
 
        m, n = len(board), len(board[0])
 
        def dfs(i: int, j: int) -> None:
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return
            board[i][j] = '#'
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)
 
        # Bước 1: đánh dấu ô an toàn reach được từ bốn biên
        for j in range(n):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[m - 1][j] == 'O':
                dfs(m - 1, j)
        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n - 1] == 'O':
                dfs(i, n - 1)
 
        # Bước 2: hoàn thiện
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0 || board[0].Length == 0) return;
 
        int m = board.Length, n = board[0].Length;
 
        void DFS(int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
            board[i][j] = '#';
            DFS(i - 1, j);
            DFS(i + 1, j);
            DFS(i, j - 1);
            DFS(i, j + 1);
        }
 
        // Bước 1: flood-fill từ tất cả ô O trên biên
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') DFS(0, j);
            if (board[m - 1][j] == 'O') DFS(m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') DFS(i, 0);
            if (board[i][n - 1] == 'O') DFS(i, n - 1);
        }
 
        // Bước 2: hoàn thiện
        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] == '#') board[i][j] = 'O';
            }
        }
    }
}

Time: O(m*n) — mỗi ô được thăm tối đa hai lần (một lần trong DFS biên, một lần trong quét cuối). Space: O(m*n) cho recursion stack trong trường hợp xấu nhất. Trong Python điều này có nghĩa DFS đệ quy vẫn có thể stack-overflow với bảng 200x200 toàn 'O'.

Trace tay qua Example 1

Board đầu vào:

X X X X
X O O X
X X O X
X O X X

Bước 1 — quét biên. Kiểm tra hàng 0: toàn 'X', không có DFS nào kích hoạt. Kiểm tra hàng 3: board[3][1] == 'O', DFS từ (3,1).

DFS (3,1): đánh dấu '#', khám phá hàng xóm. Lên là (2,1) = 'X', bỏ qua. Xuống là hàng 4, ngoài biên. Trái là (3,0) = 'X', bỏ qua. Phải là (3,2) = 'X', bỏ qua. Xong. Chỉ (3,1) được đánh dấu.

Kiểm tra cột 0 và 3: toàn 'X' trên những biên đó.

Board sau bước 1:

X X X X
X O O X
X X O X
X # X X

Bước 2 — quét cuối. 'O' tại (1,1), (1,2), (2,2) -> tất cả thành 'X'. '#' tại (3,1) -> thành 'O'.

X X X X
X X X X
X X X X
X O X X

Đúng với output kỳ vọng. 'O' tại (3,1) sống sót vì nó nằm trên biên. Cụm 'O' nội thất ở hàng 1-2 không có đường đến biên nào, nên bị capture.

Approach 3: BFS từ biên — cùng ý tưởng, không có recursion

BFS thay call stack bằng queue tường minh. Logic giống hệt — seed từ ô 'O' trên biên, đánh dấu ô reach được là '#', rồi hoàn thiện — nhưng không thể stack-overflow vì queue sống trên heap.

from collections import deque
 
class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
 
        m, n = len(board), len(board[0])
        queue: deque = deque()
 
        # Seed queue với tất cả ô O trên biên
        for i in range(m):
            for j in range(n):
                if (i == 0 or i == m - 1 or j == 0 or j == n - 1) and board[i][j] == 'O':
                    board[i][j] = '#'
                    queue.append((i, j))
 
        # BFS: mở rộng vùng an toàn
        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                    board[nx][ny] = '#'
                    queue.append((nx, ny))
 
        # Hoàn thiện
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

using System.Collections.Generic;
 
public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0 || board[0].Length == 0) return;
 
        int m = board.Length, n = board[0].Length;
        var queue = new Queue<(int, int)>();
 
        // Seed các ô O trên biên
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
                    board[i][j] = '#';
                    queue.Enqueue((i, j));
                }
            }
        }
 
        // BFS mở rộng
        int[] di = { 0, 0, 1, -1 };
        int[] dj = { 1, -1, 0, 0 };
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            for (int d = 0; d < 4; d++) {
                int nx = x + di[d], ny = y + dj[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'O') {
                    board[nx][ny] = '#';
                    queue.Enqueue((nx, ny));
                }
            }
        }
 
        // Hoàn thiện
        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] == '#') board[i][j] = 'O';
            }
        }
    }
}

Time: O(m*n), giống với DFS. Space: O(m*n) cho queue trong trường hợp xấu nhất — một vùng an toàn kết nối hoàn toàn sẽ có tất cả m*n ô trong queue tại một thời điểm. Constant tương tự với DFS stack; không có approach nào có lợi thế memory.

Các edge case thực sự quan trọng

Bảng 1x1: Ô duy nhất [["X"]] hoặc [["O"]]. Trong cả hai trường hợp, ô đó nằm trên biên. Pass biên tìm 'O' (nếu có) và đánh dấu '#'. Quét cuối khôi phục về 'O'. Không có gì bị capture — một 'O' đơn trên biên không bao giờ bị bao quanh.

Toàn 'X': Không có ô 'O' nào. Cả pass biên và quét cuối đều là no-op. Bảng không thay đổi. Code xử lý mà không cần case đặc biệt nào.

Toàn 'O': Mọi ô là 'O'. Mọi ô biên seed DFS/BFS. Traversal lan ra từ bốn cạnh cho đến khi toàn bộ bảng được đánh dấu '#'. Quét cuối khôi phục tất cả về 'O'. Không có gì bị capture vì toàn bộ bảng liên kết với biên.

Ô 'O' chỉ nằm trên biên: Các ô biên seed DFS/BFS, không tìm được hàng xóm nội thất nào (vì không có). Tất cả ô 'O' được đánh dấu '#' ngay trong phase seed. Quét cuối khôi phục chúng. Kết quả: không thay đổi.

Bảng một hàng hoặc một cột: Mọi ô đều là biên. Mọi 'O' đều an toàn. Output đúng bằng input. Code xử lý đúng vì bảng 1xN có i == 0 và i == m-1 đồng thời đúng cho mọi hàng — mọi ô là ô biên.

'O' nội thất kết nối với 'O' biên qua một hành lang: DFS/BFS theo kết nối và đánh dấu toàn bộ đường đi. Các ô nội thất không bị capture dù chúng nằm hình học "bên trong" bảng. Connectivity mới là điều quan trọng, không phải vị trí.

Bảng so sánh

Pattern nằm bên dưới, và tôi sẽ ship gì

Kỹ thuật ở đây là complement reachability: thay vì đánh dấu cái cần xóa, đánh dấu cái cần giữ, rồi xóa mọi thứ còn lại. Nó xuất hiện trong một cụm bài toán nơi tập hợp "an toàn" hoặc "reach được" dễ xác định hơn tập "không an toàn". Number of Enclaves (1020) gần như giống hệt — nó hỏi số ô nội thất không thể reach biên, chính xác là những gì bài này capture.

Mental model rộng hơn là flood fill từ seed trên boundary. Ta pre-populate traversal với tất cả ô thỏa mãn điều kiện một cách hiển nhiên (ở đây: chạm biên), để traversal mở rộng tập đó, rồi quyết định số phận các ô chưa đánh dấu trong một pass.

Giữa DFS và BFS: tôi sẽ ship BFS trong Python khi bảng có thể lên đến 200x200. Rủi ro recursion depth là thực. Trong C# nơi default stack là 1 MB và mỗi frame nhỏ, DFS đệ quy ổn và đọc đơn giản hơn một chút. Nếu bắt buộc viết một phiên bản chạy an toàn trên cả hai platform, BFS thắng.

Tôi sẽ không ship approach brute-force dù chỉ là pass đầu tiên — chi phí bậc hai đến từ câu hỏi sai ("vùng này có bị bao quanh không?") mà formulation đảo ngược loại bỏ hoàn toàn. Trong phỏng vấn, đề cập đến sự đảo ngược là insight chủ chốt mà interviewer đang lắng nghe.

Vị trí trong series graphs, và những gì tiếp theo

Series này bắt đầu với Number of Islands (200) — đếm các connected component trong grid. Bài này là bước tiếp theo: thay vì đếm component, selective capture chúng dựa trên một thuộc tính cấu trúc (khả năng reach từ biên). Flood fill nền tảng giống nhau; logic quyết định tinh tế hơn.

Number of Enclaves (1020) là cặp đôi của bài này. Nó hỏi có bao nhiêu ô nội thất không thể reach biên — đếm các ô 'O' sẽ bị capture ở đây mà không thực sự capture chúng. Cùng thuật toán, output khác.

Pacific Atlantic Water Flow (417) mở rộng ý tưởng boundary-seed sang hai boundary cùng lúc. Nước có thể chảy ra Pacific (cạnh trên/trái) và Atlantic (cạnh dưới/phải). Ta chạy hai BFS pass — một từ mỗi tập ô biên — và trả về các ô reach được từ cả hai. Sự đảo ngược ("reach được từ boundary" thay vì "không reach được từ boundary") là cùng một bước mental.

Number of Islands (200) đơn giản hơn bài này — không có điều kiện boundary, chỉ đếm component. Nếu Surrounded Regions cảm thấy thoải mái, 200 sẽ cảm thấy dễ.

Rotting Oranges (994) dùng multi-source BFS, seeding từ tất cả ô "nguồn" cùng một lúc. BFS approach trong bài này về cấu trúc giống hệt — seeding từ tất cả ô 'O' trên biên cùng một lúc. Chuyển sang 994 là bước leo thang tự nhiên.