Rotting Oranges: vì sao multi-source BFS tốt hơn simulation từng phút

Có một lớp bài toán trên grid trong đó sự lan truyền xảy ra đồng thời từ nhiều nguồn, và thứ bạn cần đo là thời gian. Rotting Oranges là ví dụ điển hình nhất. Ngay khi thấy "mỗi phút, cam tươi nào nằm kề cam thối đều thối theo cùng lúc", bạn đang nhìn vào multi-source BFS trong một lớp vỏ bọc rất mỏng.

Bài toán (LeetCode 994): cho lưới m x n trong đó 0 là ô trống, 1 là cam tươi, 2 là cam thối. Mỗi phút, mọi cam tươi nằm kề 4 hướng với một cam thối sẽ bị thối. Trả về số phút tối thiểu để không còn cam tươi nào, hoặc -1 nếu điều đó không thể xảy ra.

Constraints nói lên điều gì

1 <= m, n <= 10. Lưới lớn nhất là 10×10 = 100 ô. Rất nhỏ. Điều này có nghĩa ngay cả simulation O((m×n)²) đơn giản cũng sẽ pass thoải mái — time limit không phải thứ phân biệt hai cách tiếp cận ở đây. Điều phân biệt chúng là sự rõ ràng về mặt tư duy và những gì code dạy bạn về BFS nói chung.

Dù vậy, bounds cũng cho bạn biết điều khác: mọi approach đều chạy tính bằng millisecond trên lưới 10×10, nên benchmark chẳng có gì thú vị. Lý do học BFS ở đây là nó kết hợp gọn gàng vào các lưới 300×300 trong LeetCode 542 và 1162 — những nơi simulation chết ngay.

grid[i][j] chỉ có đúng 0, 1, hoặc 2. Không có giá trị nào khác, không cần kiểm tra đầu vào. Điều này cho phép mutate grid tại chỗ — lật cam tươi thành 2 khi bị nhiễm, để không bao giờ quay lại nó nữa. Không cần tập visited riêng, không tốn thêm O(m×n) space ngoài queue.

Kề 4 hướng, không phải 8. Đường chéo không lan truyền. Đáng nêu rõ vì đây là loại constraint mà nếu đọc nhầm sẽ cho kết quả sai mặc dù đa số test case vẫn đúng.

Simulation: brute force thành thật

Cách đọc thẳng thắn nhất của đề bài là mô phỏng nó theo nghĩa đen: mỗi phút, quét toàn bộ lưới, đánh dấu mọi cam tươi kề cam thối là mới thối, rồi lặp lại cho đến khi không còn thay đổi nào nữa.

Điểm khó ở đây là bạn không thể cập nhật tại chỗ trong khi đang quét — nếu bạn lật một cam tươi thành thối giữa chừng ở phút 1, nó sẽ nhiễm cho hàng xóm trong cùng lần quét đó, vốn là sai. Mọi thứ trong cùng một phút phải lan ra đồng thời. Vì vậy simulation sao chép lưới vào đầu mỗi phút, đọc từ bản gốc và ghi vào bản mới.

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        minutes = 0
 
        while True:
            new_grid = [row[:] for row in grid]
            changed = False
 
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 1:
                        for di, dj in directions:
                            ni, nj = i + di, j + dj
                            if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 2:
                                new_grid[i][j] = 2
                                changed = True
                                break
 
            if not changed:
                break
 
            grid = new_grid
            minutes += 1
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    return -1
 
        return minutes

public class Solution {
    public int OrangesRotting(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int minutes = 0;
 
        while (true) {
            int[][] newGrid = new int[rows][];
            for (int i = 0; i < rows; i++) {
                newGrid[i] = new int[cols];
                Array.Copy(grid[i], newGrid[i], cols);
            }
 
            bool changed = false;
 
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == 1) {
                        for (int d = 0; d < 4; d++) {
                            int ni = i + directions[d, 0];
                            int nj = j + directions[d, 1];
                            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 2) {
                                newGrid[i][j] = 2;
                                changed = true;
                                break;
                            }
                        }
                    }
                }
            }
 
            if (!changed) break;
 
            grid = newGrid;
            minutes++;
        }
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 1) return -1;
 
        return minutes;
    }
}

Độ phức tạp: Mỗi phút tốn O(m×n) để quét. Trong trường hợp xấu nhất, sự nhiễm trùng lan một ô mỗi phút trên toàn bộ lưới — tối đa m×n phút, cho ra O((m×n)²) thời gian. Space là O(m×n) cho bản sao lưới.

Trên lưới 10×10 là tối đa 10,000 phép tính. Không đáng kể. Nhưng trên lưới 1,000×1,000 (giả sử), simulation sẽ cần 10^12 phép tính. Và đó là nơi nó chết.

BFS: một lượt, xong

Insight giúp BFS tốt hơn: sự lan truyền đồng thời chính xác là thứ BFS mô hình hóa một cách tự nhiên. BFS xử lý ô theo từng level — một level đầy đủ mỗi phút. Bắt đầu với mọi cam thối đã có trong queue (đó là phần "multi-source"), rồi để BFS chạy. Level 1 nhiễm tất cả hàng xóm tươi của các cam thối ban đầu. Level 2 nhiễm hàng xóm của chúng. Cứ vậy tiếp tục.

Không quét lặp lại. Không sao chép lưới. Mỗi ô vào queue nhiều nhất một lần.

from collections import deque
 
class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh_count += 1
 
        if fresh_count == 0:
            return 0
 
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        minutes = 0
 
        while queue and fresh_count > 0:
            minutes += 1
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh_count -= 1
                        queue.append((nr, nc))
 
        return minutes if fresh_count == 0 else -1

using System.Collections.Generic;
 
public class Solution {
    public int OrangesRotting(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        var queue = new Queue<(int, int)>();
        int freshCount = 0;
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) queue.Enqueue((i, j));
                else if (grid[i][j] == 1) freshCount++;
            }
        }
 
        if (freshCount == 0) return 0;
 
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int minutes = 0;
 
        while (queue.Count > 0 && freshCount > 0) {
            minutes++;
            int levelSize = queue.Count;
            for (int i = 0; i < levelSize; i++) {
                var (row, col) = queue.Dequeue();
                for (int d = 0; d < 4; d++) {
                    int nr = row + directions[d, 0];
                    int nc = col + directions[d, 1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        freshCount--;
                        queue.Enqueue((nr, nc));
                    }
                }
            }
        }
 
        return freshCount == 0 ? minutes : -1;
    }
}

Độ phức tạp: Lượt quét ban đầu là O(m×n). Bản thân BFS thăm mỗi ô nhiều nhất một lần — một khi cam tươi vào queue, nó ngay lập tức được đánh dấu thối và không bao giờ bị xếp hàng lại. Tổng cộng: O(m×n) thời gian, O(m×n) space cho queue trong trường hợp xấu nhất (tất cả ô đều thối cùng lúc).

Trace tay ví dụ 1

Lưới: [[2,1,1],[1,1,0],[0,1,1]]

Thiết lập ban đầu: một cam thối tại (0,0). Sáu cam tươi ở những nơi còn lại.

Phút 1 xử lý level {(0,0)}. Nó nhiễm (0,1) bên phải và (1,0) bên dưới. Queue giờ là {(0,1), (1,0)}. Fresh count giảm còn 4.

Phút 2 xử lý {(0,1), (1,0)}. (0,1) nhiễm (0,2). (1,0) nhiễm (1,1). Queue: {(0,2), (1,1)}. Fresh count: 2.

Phút 3 xử lý {(0,2), (1,1)}. (0,2) không có hàng xóm tươi (phải ngoài biên, dưới là (1,2) tức là 0). (1,1) nhiễm (2,1). Queue: {(2,1)}. Fresh count: 1.

Phút 4 xử lý {(2,1)}. Nó nhiễm (2,2). Queue rỗng. Fresh count: 0. Trả về 4.

Lưu ý (1,2) là 0 — ô trống, không phải cam tươi. Nó không bao giờ bị chạm vào. BFS tự nhiên bỏ qua nó vì chúng ta chỉ xếp hàng ô có grid[nr][nc] == 1.

Các trường hợp phá vỡ implementation ngây thơ

Không có cam tươi ngay từ đầu. [[0,2]] — fresh count là 0 sau lượt quét ban đầu. Chúng ta trả về 0 ngay lập tức, trước khi chạm vào queue. Đây là edge case thường bị quên nhất nếu bạn chỉ kiểm tra "queue có rỗng không" ở cuối.

Cam tươi nhưng không có cam thối. [[1,1],[1,1]] — fresh count là 4, queue rỗng. Vòng lặp BFS không bao giờ chạy. Sau vòng lặp, fresh count vẫn là 4, vì vậy chúng ta trả về -1. Code xử lý điều này mà không cần case đặc biệt.

Cam tươi bị cô lập. [[2,1,1],[0,1,1],[1,0,1]] — cam ở (2,0) bị bao quanh bởi ô trống trên mọi phía có thể tiếp cận. BFS chạy hết hoàn toàn mà không bao giờ chạm tới nó. Fresh count là 1 ở cuối, nên chúng ta trả về -1. Điểm mấu chốt là chúng ta theo dõi fresh_count riêng biệt thay vì dựa vào queue — khi queue rỗng, chúng ta kiểm tra xem có gì bị bỏ sót không.

Lưới một ô. [[2]] chạm vào guard fresh_count == 0 và trả về 0. [[1]] có fresh count là 1 và queue rỗng — BFS không bao giờ chạy và chúng ta trả về -1. [[0]] trả về 0 vì không có cam tươi nào để lo.

Tất cả ô đều thối. Trả về 0 ngay lập tức qua guard fresh_count == 0.

Simulation vs BFS — cái nào nên dùng

Với bài toán cụ thể này và constraint 10×10, tôi vẫn sẽ chọn BFS. Không phải vì simulation bị fail — nó không fail — mà vì BFS thực sự ngắn hơn khi bạn đã thấm pattern level-by-level. Vòng lặp simulation dài hơn và cấp phát một bản sao lưới đầy đủ mỗi phút. BFS chỉ là một lượt duyệt duy nhất.

Có một phiên bản BFS tôi hay thấy bỏ qua trick len(queue) và chỉ tăng minutes ở cuối vòng lặp BFS. Cách đó sai. Bạn sẽ bị lệch một phút hoặc đếm thêm phút cho level rỗng. Snapshot kích thước level ở đầu mỗi lần lặp BFS — for _ in range(len(queue)) trong Python hoặc int levelSize = queue.Count trong C# — là phần quan trọng không thể thiếu. Đó là thứ làm cho BFS xử lý đúng một phút cam thối mỗi lần.

Pattern multi-source BFS

Mental model ở đây là: "Tôi có nhiều điểm xuất phát và muốn biết thời gian tối thiểu để một làn sóng chạm đến mọi ô có thể tiếp cận." Đó là multi-source BFS. Bạn seed queue với tất cả các nguồn cùng một lúc. Mỗi level của BFS là một bước thời gian. Độ sâu mà một ô được chạm đến lần đầu tiên chính là khoảng cách tối thiểu của nó từ bất kỳ nguồn nào.

Pattern này giải quyết một họ bài toán cụ thể:

• 542. 01 Matrix: tìm khoảng cách ngắn nhất từ mỗi ô đến 0 gần nhất. Cùng cấu trúc — seed queue với mọi 0, BFS lan ra ngoài. Thay vì đếm cam, bạn ghi lại khoảng cách khi mỗi ô được chạm đến lần đầu.
• 286. Walls and Gates: điền vào mỗi phòng trống khoảng cách đến gate gần nhất. Seed với tất cả gates, BFS lan ra.
• 1162. As Far from Land as Possible: tìm ô xa nhất so với bất kỳ ô đất nào. Seed với tất cả ô đất, BFS cho đến khi ô nước cuối cùng được chạm — bộ đếm phút lúc đó chính là đáp án.
• 1091. Shortest Path in Binary Matrix: single source lần này, nhưng cơ chế BFS-trên-grid giống hệt. Twist là di chuyển 8 hướng và chướng ngại vật nhị phân.

Trong mỗi trường hợp, câu hỏi quan trọng là: cái gì vào queue lúc đầu? Các nguồn. Mỗi level BFS đại diện cho điều gì? Một đơn vị thời gian, hoặc một đơn vị khoảng cách. Tín hiệu hoàn thành là gì? Queue rỗng hoặc bạn chạm đến một mục tiêu cụ thể.

Rotting Oranges thêm một chi tiết mà các bài đơn giản hơn không có: bạn cần biết liệu BFS có thể không chạm đến mọi cam tươi không. Vì vậy fresh_count tồn tại. Đó là thước đo "làn sóng có phủ khắp mọi thứ có thể tiếp cận không?" Nếu BFS xong mà fresh_count > 0, một số cam bị bao quanh bởi ô trống và sẽ không bao giờ thối.

Series tiếp tục với course schedule, nơi graph là tường minh (adjacency list, không phải grid) và câu hỏi không phải khoảng cách mà là khả năng tiếp cận — cụ thể là liệu có cycle tồn tại không. Logic BFS cơ bản là như nhau; thứ thay đổi là cách biểu diễn.