Phỏng vấn 3: BFS, DFS, Dijkstra trên ma trận
Luyện phỏng vấn đồ thị: flood fill, số đảo, đường ngắn nhất lưới, Dijkstra có trọng số và bẫy thăm lại.
KhóThuật toán ~90 phút
Ôn lại trước khi học
Giới thiệu
Bạn luyện bài đồ thị trên lưới. Vẽ lưới và đánh số thứ tự thăm.
Kiến thức cần nhớ
Flood fill và đếm đảo
- Flood fill tô lan từ một ô sang ô kề.
- Đếm đảo là đếm vùng đất liền nhau.
- Ví dụ đời thường: giống đổ sơn loang trên giấy.
- Mỗi ô chỉ tô đúng một lần.
BFS đường ngắn nhất
- BFS trên lưới tìm đường ít bước nhất.
- Mê cung và lan nhiều nguồn đều dùng BFS.
- Ví dụ đời thường: giống sóng lan từ tâm ra.
- Đích bị bao kín thì kết luận không có đường.
Dijkstra và bẫy thăm lại
- Ô có chi phí khác nhau thì dùng Dijkstra.
- Đánh dấu trước khi cho vào hàng đợi.
- Ví dụ đời thường: giống đi đường thu phí, chọn rẻ nhất.
- Đánh dấu muộn dễ cho một ô vào hàng đợi nhiều lần.
# đếm đảo bằng flood fill
def dem_dao(luoi):
dem = 0 # số đảo tìm được
for i in range(len(luoi)): # duyệt từng hàng
for j in range(len(luoi[0])): # duyệt từng cột
if luoi[i][j] == 1: # gặp đất mới
dem += 1 # thêm một đảo
luoi[i][j] = 0 # đánh dấu đã thăm
return dem
Ví dụ
- Lưới có đảo chạm biên và đảo một ô -> đếm đủ cả hai.
- Đích bị ô chặn bao kín -> BFS báo không có đường.
💻 Bài tập
Luyện phỏng vấn, mỗi bài 25 phút. Nộp vào day-163/, mỗi bài 1 file có test và comment độ phức tạp.
Bài 1: Flood fill và đếm vùng
| Bài | Đề |
|---|---|
| 1a | Đếm số đảo trong lưới '1'/'0' |
| 1b | Diện tích đảo lớn nhất |
| 1c | Tô màu flood fill từ ô (sr, sc) |
| 1d | Lật mọi vùng 'O' bị 'X' bao kín thành 'X' (vùng chạm biên giữ nguyên) |
1a: [["1","1","0"],["1","0","0"],["0","0","1"]] -> 2
Viết cả bản BFS và DFS cho 1a. Bản DFS đệ quy trên lưới toàn '1': ghi lại hiện tượng.
Bài 2: BFS đường ngắn nhất
| Bài | Đề |
|---|---|
| 2a | Đường ngắn nhất trong ma trận nhị phân, đi 8 hướng |
| 2b | Cam thối lan: mỗi phút cam thối làm thối cam kề. Bao nhiêu phút để thối hết, không được thì -1 (BFS đa nguồn) |
| 2c | Biến từ begin thành end, mỗi bước đổi 1 chữ, từ trung gian phải có trong từ điển. Số bước ít nhất |
2b: [[2,1,1],[1,1,0],[0,1,1]] -> 4
2c: hit -> cog, dict [hot,dot,dog,lot,log,cog] -> 5
Bài 3: Chi phí và phụ thuộc (nâng cao)
- Lưới chi phí: đường từ góc trên trái tới dưới phải có tổng chi phí nhỏ nhất, đi 4 hướng (Dijkstra).
- Lưới độ cao: đường có chênh lệch độ cao lớn nhất nhỏ nhất (Dijkstra biến thể hoặc binary search + BFS).
- Có hoàn thành được mọi môn học với danh sách môn tiên quyết không? In một thứ tự học (topo sort).
✅ Tiêu chí hoàn thành
- 10 bài có test gồm lưới rỗng, lưới 1 ô, đích bị bao kín.
- Đánh dấu thăm lúc đẩy vào hàng đợi, có comment giải thích.
- Ghi lại hiện tượng tràn stack của DFS đệ quy.
- Bảng thời gian thực tế mỗi bài.
❓ Câu hỏi ôn tập
- Flood fill lan sang ô nào?
- BFS hợp lưới loại nào?
- Ô có trọng số dùng gì?
- Đánh dấu trước hay sau khi xếp hàng?
🌕 Bạn đã hoàn thành ngày 163. Làm hết bài tập phía trên rồi sang ngày tiếp theo.