Phỏng vấn

Bài toán số hòn đảo (Number of Islands) và mẫu loang trên lưới

Trên ma trận 2D gồm đất liền và mặt nước, mỗi hòn đảo thực chất là một thành phần liên thông của đồ thị lưới 4 hướng. Nắm vững kỹ thuật loang (Flood Fill) bằng BFS hoặc DFS và thời điểm đánh dấu ô đã thăm sẽ giúp bạn giải trọn chuỗi bài Number of Islands, Max Area of Island và Rotting Oranges.

Nhận diện bài toán đồ thị ngầm trên lưới 2D và hợp đồng cần hỏi rõ

Trong phỏng vấn tại Amazon, Google và Meta, rất nhiều bài toán đồ thị không hề cho danh sách cạnh (u, v) tường minh mà ẩn dưới dạng một bảng lưới hai chiều (2D Grid / Matrix) kích thước \(H \times W\). Tiêu biểu nhất là bài toán Number of Islands: cho lưới gồm các ký tự '1' (đất liền) và '0' (nước), hãy đếm số lượng hòn đảo, biết rằng hai ô đất thuộc cùng một đảo nếu chúng chung cạnh theo chiều ngang hoặc chiều dọc.

Khi dịch từ ngôn ngữ đời thường sang ngôn ngữ lý thuyết đồ thị:

  • Mỗi ô đất (r, c) có grid[r][c] == '1' là một đỉnh (vertex).
  • Hai ô đất kề nhau có một cạnh vô hướng (undirected edge) nối giữa chúng.
  • Số lượng hòn đảo chính là số thành phần liên thông (connected components) của đồ thị lưới này!

Trước khi cài đặt, bạn hãy hỏi rõ người phỏng vấn 3 điểm sau:

  1. Quy ước kề 4 hướng hay 8 hướng? Trong chuẩn bài Number of Islands trên LeetCode, hai ô chỉ tính là nối với nhau theo 4 hướng (trên, dưới, trái, phải: di = {1, -1, 0, 0}, dj = {0, 0, 1, -1}), còn chạm nhau theo đường chéo thì vẫn là hai đảo riêng biệt. Tuy nhiên, một số biến thể trên GeeksforGeeks hoặc bài dò mìn lại tính cả 8 hướng, nên xác nhận trước luôn là bước bắt buộc.
  2. Có được phép sửa trực tiếp ma trận đầu vào grid không? Nếu được phép, bạn có thể "nhấn chìm" mỗi ô đất đã thăm bằng cách gán thẳng grid[r][c] = '0' để tiết kiệm toàn bộ mảng đánh dấu visited[H][W]. Nếu không được làm thay đổi dữ liệu gốc của hệ thống, bạn cần tạo mảng bool visited[H][W] riêng (hoặc đổi tạm thành '2' rồi khôi phục lại '1' ở cuối hàm).
  3. Kích thước lưới tối đa là bao nhiêu? Nếu lưới có thể lớn tới \(1000 \times 1000\) (\(10^6\) ô) và toàn bộ lưới là chữ '1', gọi DFS đệ quy sâu \(10^6\) mức sẽ làm tràn ngăn xếp (Stack Overflow) trong C++, Python và Java! Khi đó BFS dùng hàng đợi (hoặc DFS khử đệ quy) là lựa chọn an toàn hơn hẳn.
Ý chính

Trong thuật toán loang (Flood Fill) bằng BFS trên lưới, nguyên tắc sống còn là phải đánh dấu ô kề (nr, nc) đã thăm ngay tại thời điểm đẩy vào hàng đợi (q.push), tuyệt đối không đợi tới lúc lấy ra khỏi hàng đợi (q.pop) mới đánh dấu. Đánh dấu muộn sẽ khiến cùng một ô bị đẩy vào hàng đợi nhiều lần từ các hướng khác nhau, gây nổ bộ nhớ và quá thời gian.

Number of Islands trên lưới 4×5: 3 hòn đảo (kề 4 hướng) Hai ô '1' chạm nhau theo đường chéo KHÔNG nối thành cùng một đảo 11000110000010000011 Đảo #1 (xanh dương): 4 ô đất Khối 2×2 ở góc trên trái → Max Area = 4 Đảo #2 (xanh lá): 1 ô tại (2, 2) Cô lập 4 hướng (trên, dưới, trái, phải = 0) Đảo #3 (cam): 2 ô tại (3, 3..4) Nối ngang ở hàng cuối → diện tích = 2 Đánh dấu grid[nr][nc] = '0' ngay khi đẩy vào Queue · Độ phức tạp O(H · W)
Number of Islands: Lưới 4×5 3 đảo độc lập · Diện tích lớn nhất = 4 Đảo #1: (0,0), (0,1), (1,0), (1,1) Diện tích = 4 ô (lớn nhất) Đảo #2: ô đơn độc (2, 2) Diện tích = 1 ô (không nối chéo) Đảo #3: (3, 3) và (3, 4) Diện tích = 2 ô (kề ngang) BFS/DFS loang 4 hướng · O(H · W)
Hình 1. Quá trình loang Flood Fill 4 hướng trên lưới 4x5 tách biệt rõ 3 hòn đảo: Đảo #1 ở góc trên trái có diện tích 4 ô, Đảo #2 ở ô (2, 2) đứng riêng với diện tích 1 ô (vì đường chéo không nối), và Đảo #3 ở hàng cuối có diện tích 2 ô.

Cơ chế loang Flood Fill: Đếm số đảo và tính diện tích đảo lớn nhất

Thuật toán kết hợp hai bài toán kinh điển Number of Islands (đếm số đảo) và Max Area of Island (diện tích hòn đảo lớn nhất) chỉ trong một lượt quét hai vòng lặp for:

  1. Duyệt tuần tự từng ô (i, j) từ dòng 0 đến H - 1, cột 0 đến W - 1.
  2. Nếu grid[i][j] == '0' (nước hoặc đất đã được loang qua trước đó), ta bỏ qua ngay.
  3. Nếu grid[i][j] == '1', ta vừa tìm thấy "mầm" của một hòn đảo hoàn toàn mới:
    • Tăng biến đếm số đảo islands++ và khởi tạo diện tích đảo hiện tại area = 0.
    • Khởi tạo hàng đợi q, đẩy (i, j) vào và đánh dấu ngay grid[i][j] = '0'.
    • Trong khi q chưa rỗng: lấy ô (r, c) ra, tăng area++, rồi xét 4 ô láng giềng (nr, nc). Nếu (nr, nc) nằm trong biên lưới và grid[nr][nc] == '1', ta đánh dấu ngay grid[nr][nc] = '0' rồi đẩy (nr, nc) vào q.
    • Khi hàng đợi rỗng, toàn bộ các ô đất nối với (i, j) đã bị xóa thành '0' và biến area giữ đúng số ô của đảo đó. Ta cập nhật max_area = max(max_area, area).

Chạy tay từng bước trên lưới 4x5

Xét lưới \(4 \times 5\) trong Hình 1 với 4 dòng: "11000", "11000", "00100", "00011". Dưới đây là diễn biến của hai vòng lặp ngoài và các đợt loang BFS bên trong:

Lượt loang Ô kích hoạt (i, j) Trình tự các ô lấy ra khỏi hàng đợi q Các ô láng giềng '1' mới được đẩy vào q Diện tích area của đảo Cập nhật (islands, max_area)
Đảo #1 (0, 0) 1. Lấy (0, 0)
2. Lấy (1, 0)
3. Lấy (0, 1)
4. Lấy (1, 1)
Từ (0,0) đẩy (1,0) và (0,1)
Từ (1,0) đẩy (1,1)
Từ (0,1) thấy (1,1) đã thành '0' nên không đẩy trùng!
Từ (1,1) không còn ô '1' kề
4 ô islands = 1, max_area = 4
Đảo #2 (2, 2) 1. Lấy (2, 2) Cả 4 hướng (1,2), (3,2), (2,1), (2,3) đều là '0'; hai ô (1,1) và (3,3) chỉ chạm chéo nên không xét 1 ô islands = 2, max_area = 4
Đảo #3 (3, 3) 1. Lấy (3, 3)
2. Lấy (3, 4)
Từ (3,3) đẩy (3,4)
Từ (3,4) không còn ô '1' kề
2 ô islands = 3, max_area = 4

Chú ý ở bước thứ 3 của Đảo #1: khi đứng tại (0, 0), cả (1, 0) và (0, 1) đều cùng kề với ô (1, 1). Nhờ ta đã đổi grid[1][1] = '0' ngay lúc đứng ở (1, 0) để đẩy (1, 1) vào hàng đợi, khi tới lượt (0, 1) nhìn xuống (1, 1) thì ô đó đã là '0' nên không bị đẩy vào hàng đợi lần thứ hai.

Code mẫu C++17, Python và Java 21

Chương trình dưới đây đọc kích thước lưới h, w và h chuỗi nhị phân, chạy thuật toán BFS loang 4 hướng để in ra đồng thời <số lượng hòn đảo> <diện tích hòn đảo lớn nhất>.

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w;
    if (!(cin >> h >> w)) return 0;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];

    int islands = 0, max_area = 0;
    const int di[4] = {1, -1, 0, 0};
    const int dj[4] = {0, 0, 1, -1};

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j] == '1') {
                islands++;
                int area = 0;
                queue<pair<int, int>> q;
                q.push({i, j});
                g[i][j] = '0';
                while (!q.empty()) {
                    auto [r, c] = q.front();
                    q.pop();
                    area++;
                    for (int k = 0; k < 4; k++) {
                        int nr = r + di[k], nc = c + dj[k];
                        if (nr >= 0 && nr < h && nc >= 0 && nc < w && g[nr][nc] == '1') {
                            g[nr][nc] = '0';
                            q.push({nr, nc});
                        }
                    }
                }
                max_area = max(max_area, area);
            }
        }
    }
    cout << islands << ' ' << max_area << '\n';
    return 0;
}

Độ phức tạp thời gian và bộ nhớ

  • Thời gian: O(H * W). Hai vòng lặp ngoài nhìn qua mỗi ô đúng 1 lần. Mỗi ô có giá trị '1' được đẩy vào hàng đợi q đúng 1 lần và lấy ra đúng 1 lần; khi lấy ra chỉ kiểm tra đúng 4 hướng kề trong O(1). Do đó tổng số phép toán tỷ lệ tuyến tính với tổng số ô của lưới.
  • Bộ nhớ phụ:
    • Nếu đánh dấu trực tiếp lên grid: bộ nhớ phụ chỉ còn hàng đợi BFS, chứa các ô ở mặt sóng loang. Với lưới toàn '1' loang từ góc, mặt sóng là đường chéo nên hàng đợi không quá min(H, W) + 1 ô; nhưng với đảo có hình phân nhánh, rất nhiều ô cách ô xuất phát cùng một khoảng nên hàng đợi có thể chứa số ô tỉ lệ với H * W (ví dụ một đảo hình cây phân nhánh kiểu chữ H trên lưới 255 x 255 làm hàng đợi chứa tới 2048 ô, gấp 8 lần min(H, W)). Cận đúng cho trường hợp xấu nhất là O(H * W).
    • Nếu dùng DFS đệ quy: bộ nhớ ngăn xếp trong trường hợp xấu nhất (lưới toàn '1' đi theo đường zíc-zắc) là O(H * W).

Từ loang đơn nguồn đến BFS đa nguồn (Rotting Oranges) và Loang từ biên

Nắm vững khung loang trên lưới 2D giúp bạn mở khóa ngay 5 bài toán phỏng vấn cực kỳ phổ biến cùng họ:

Bài toán phỏng vấn Điểm khác biệt cốt lõi so với Number of Islands Cách điều chỉnh thuật toán
Max Area of Island Cần đếm số ô của từng thành phần liên thông Cộng biến area++ mỗi khi pop một ô khỏi hàng đợi và lấy max qua các đảo
Surrounded Regions / Number of Closed Islands Các vùng chạm vào 4 viền ngoài cùng của ma trận thì không bị tính là bị bao vây Loang ngược từ biên: Chạy Flood Fill từ mọi ô 'O' nằm trên hàng 0, H-1 và cột 0, W-1 để đánh dấu các vùng thoát ra biên trước, phần còn lại bên trong chính là vùng bị vây kín
Pacific Atlantic Water Flow Tìm các ô mà nước có thể chảy tới cả bờ Thái Bình Dương (trên, trái) và Đại Tây Dương (dưới, phải) Chạy 2 lượt BFS/DFS đi ngược chiều dốc (height[nr][nc] >= height[r][c]): một lượt xuất phát từ toàn bộ viền Thái Bình Dương, một lượt từ viền Đại Tây Dương, rồi lấy giao của 2 tập hợp
Rotting Oranges / 01 Matrix / Walls and Gates Cần tính số phút tối thiểu để cam thối lan ra toàn bộ cam tươi BFS đa nguồn theo từng tầng: Đẩy tất cả các quả cam thối ban đầu vào hàng đợi q cùng lúc ở phút 0, sau đó dùng mẫu sz = q.size() loang từng lớp 1 phút
Number of Islands II (Thêm đất động) Các ô đất được thêm vào lần lượt qua k truy vấn, hỏi số đảo sau mỗi lần thêm Không thể BFS lại từ đầu sau mỗi truy vấn; dùng cấu trúc Disjoint Set Union (DSU / Union-Find): mỗi ô đất mới tạo thêm 1 đảo, rồi union với 4 ô đất kề (mỗi lần gộp thành công giảm số đảo đi 1)

Đặc biệt với bài Cam thối (Rotting Oranges), người phỏng vấn rất hay hỏi vì sao bắt buộc phải dùng BFS đa nguồn mà không dùng DFS được. Lý do là các quả cam thối lan truyền đồng thời theo từng phút (tương đương khoảng cách đường đi ngắn nhất trên đồ thị không trọng số); chỉ khi đẩy toàn bộ các nguồn ban đầu vào hàng đợi ở tầng 0 và loang theo từng lớp sz = q.size(), mỗi quả cam tươi mới nhận được đúng thời điểm bị lây nhiễm sớm nhất.

Những lỗi sai kinh điển và cách tự kiểm tra code

  1. Đánh dấu visited khi lấy ra khỏi q thay vì khi đẩy vào q: Với lưới \(300 \times 300\) toàn số '1', nếu bạn chỉ gán grid[r][c] = '0' sau lệnh q.pop(), mỗi ô (r, c) sẽ bị cả người hàng xóm phía trên và người hàng xóm bên trái cùng đẩy vào q trước khi nó kịp được lấy ra, làm số phần tử trong q tăng theo cấp số nhân ở các bước đầu và gây Time Limit Exceeded hoặc Memory Limit Exceeded.
  2. So sánh nhầm kiểu ký tự '1' và số nguyên 1: Trong bài Number of Islands, ma trận đầu vào thường là vector<vector<char>> (chứa ký tự '1' có mã ASCII là 49, khác hoàn toàn số 1), trong khi bài Max Area of Island lại cho vector<vector<int>>. Nếu viết if (grid[i][j] == 1) trên mảng char, điều kiện sẽ luôn sai và trả về 0 đảo!
  3. Quên kiểm tra biên 0 <= nr < H && 0 <= nc < W trước khi đọc grid[nr][nc]: Trong C++, truy cập grid[-1][0] gây hành vi bất định (Undefined Behavior); còn trong Python, chỉ số âm grid[-1][0] lại hợp lệ và vòng xuống dòng cuối cùng của ma trận, nối nhầm dòng đầu với dòng cuối thành một đảo hình trụ cực kỳ khó tìm lỗi! Trong Python, bạn bắt buộc phải kiểm tra 0 <= nr < h and 0 <= nc < w.

Để tự kiểm tra code, bạn có thể đối chiếu kết quả của hàm BFS với một hàm dùng cấu trúc Union-Find (DSU) độc lập trên 3 bộ test biên:

  • Lưới toàn nước '0' (3x3 toàn '0' → 0 đảo, diện tích lớn nhất 0).
  • Lưới toàn đất '1' (2x2 toàn '1' → 1 đảo duy nhất, diện tích 4).
  • Lưới có các ô '1' nằm trên đường chéo như Hình 1 (4x5 → 3 đảo, diện tích lớn nhất 4).

Thêm một lưới 3x3 chỉ có 4 ô góc là đất (101, 000, 101 → 4 đảo, diện tích lớn nhất 1): bản Python quên chặn 0 <= nr và 0 <= nc sẽ nối nhầm 4 góc thành 1 đảo 4 ô.

Luyện ngay trên Big-O Coding

Hãy thực hành ngay kỹ thuật loang trên lưới và duyệt đồ thị qua 3 bài toán phỏng vấn kinh điển trong lộ trình Coding Interview 150 dưới đây.

Câu hỏi thường gặp

Giữa BFS và DFS đệ quy cho bài Number of Islands, khi đi phỏng vấn nên viết cách nào?

Bạn có thể viết DFS đệ quy trước nếu muốn code cực ngắn (chỉ khoảng 10 dòng) và dễ giải thích trên bảng trắng, nhưng hãy chủ động nói ngay với người phỏng vấn: "Với lưới rất lớn cỡ \(1000 \times 1000\), DFS đệ quy có thể tràn bộ nhớ ngăn xếp tới \(O(H \cdot W)\), nên trong môi trường sản xuất em sẽ ưu tiên chuyển sang BFS dùng hàng đợi như bản cài đặt này." Câu nói đó giúp bạn ghi điểm tuyệt đối cả về tốc độ code lẫn tư duy kỹ thuật thực chiến.

Tại sao trong Python viết grid[-1][0] khi quên chặn nr >= 0 lại nguy hiểm hơn trong C++ hay Java?

Trong Java, truy cập chỉ số -1 sẽ ném ngay ngoại lệ ArrayIndexOutOfBoundsException giúp bạn phát hiện lỗi tức thì. Ngược lại, trong Python, danh sách hỗ trợ chỉ số âm để lấy phần tử tính từ cuối mảng (grid[-1] chính là hàng cuối cùng grid[h - 1]). Do đó chương trình Python không hề báo lỗi mà âm thầm nối các ô ở hàng đầu tiên với hàng cuối cùng và cột đầu tiên với cột cuối cùng!

Khi nào bài toán trên lưới không dùng được BFS thường mà phải dùng thuật toán Dijkstra?

Bạn chỉ dùng được BFS hàng đợi thường khi mọi bước di chuyển sang ô kề đều có cùng chi phí bằng 1 (như đếm số bước ngắn nhất hoặc thời gian cam thối). Nếu mỗi ô trên lưới mang một trọng số chi phí khác nhau (ví dụ độ cao cần leo hoặc thời gian chờ tại từng ô như bài Swim in Rising Water hay Path With Minimum Effort), bạn cần thay hàng đợi thường bằng Hàng đợi ưu tiên (Min-Heap — thuật toán Dijkstra) hoặc dùng BFS 0-1 (Deque) nếu trọng số cạnh chỉ nhận hai giá trị 0 và 1.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483