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:
- 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. - Có được phép sửa trực tiếp ma trận đầu vào
gridkhô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ẳnggrid[r][c] = '0'để tiết kiệm toàn bộ mảng đánh dấuvisited[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ảngbool 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). - 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.
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.
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:
- Duyệt tuần tự từng ô
(i, j)từ dòng0đếnH - 1, cột0đếnW - 1. - Nếu
grid[i][j] == '0'(nước hoặc đất đã được loang qua trước đó), ta bỏ qua ngay. - 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ạiarea = 0. - Khởi tạo hàng đợi
q, đẩy(i, j)vào và đánh dấu ngaygrid[i][j] = '0'. - Trong khi
qchưa rỗng: lấy ô(r, c)ra, tăngarea++, 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 ngaygrid[nr][nc] = '0'rồi đẩy(nr, nc)vàoq. - 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ếnareagiữ đúng số ô của đảo đó. Ta cập nhậtmax_area = max(max_area, area).
- Tăng biến đếm số đảo
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;
}
import collections
import sys
def main() -> None:
tokens = sys.stdin.read().split()
if len(tokens) < 2:
return
h, w = int(tokens[0]), int(tokens[1])
grid = [list(tokens[2 + i]) for i in range(h)]
islands = 0
max_area = 0
for i in range(h):
for j in range(w):
if grid[i][j] == "1":
islands += 1
area = 0
q = collections.deque([(i, j)])
grid[i][j] = "0"
while q:
r, c = q.popleft()
area += 1
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] == "1":
grid[nr][nc] = "0"
q.append((nr, nc))
max_area = max(max_area, area)
print(f"{islands} {max_area}")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int h = sc.nextInt();
int w = sc.nextInt();
char[][] g = new char[h][w];
for (int i = 0; i < h; i++) {
g[i] = sc.next().toCharArray();
}
int islands = 0, maxArea = 0;
int[] di = {1, -1, 0, 0};
int[] dj = {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;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{i, j});
g[i][j] = '0';
while (!q.isEmpty()) {
int[] cur = q.remove();
area++;
for (int k = 0; k < 4; k++) {
int nr = cur[0] + di[k], nc = cur[1] + dj[k];
if (nr >= 0 && nr < h && nc >= 0 && nc < w && g[nr][nc] == '1') {
g[nr][nc] = '0';
q.add(new int[]{nr, nc});
}
}
}
maxArea = Math.max(maxArea, area);
}
}
}
System.out.println(islands + " " + maxArea);
}
}
Độ 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 đợiqđú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ề trongO(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ớiH * W(ví dụ một đảo hình cây phân nhánh kiểu chữ H trên lưới255 x 255làm hàng đợi chứa tới2048ô, gấp 8 lầnmin(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).
- Nếu đánh dấu trực tiếp lên
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
- Đánh dấu
visitedkhi lấy ra khỏiqthay vì khi đẩy vàoq: Với lưới \(300 \times 300\) toàn số'1', nếu bạn chỉ gángrid[r][c] = '0'sau lệnhq.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àoqtrước khi nó kịp được lấy ra, làm số phần tử trongqtăng theo cấp số nhân ở các bước đầu và gây Time Limit Exceeded hoặc Memory Limit Exceeded. - So sánh nhầm kiểu ký tự
'1'và số nguyên1: 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 chovector<vector<int>>. Nếu viếtif (grid[i][j] == 1)trên mảngchar, điều kiện sẽ luôn sai và trả về0đảo! - Quên kiểm tra biên
0 <= nr < H && 0 <= nc < Wtrước khi đọcgrid[nr][nc]: Trong C++, truy cậpgrid[-1][0]gây hành vi bất định (Undefined Behavior); còn trong Python, chỉ số âmgrid[-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 tra0 <= 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'(3x3toàn'0'→0đảo, diện tích lớn nhất0). - Lưới toàn đất
'1'(2x2toàn'1'→1đảo duy nhất, diện tích4). - 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ất4).
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.
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.


