BFS, DFS và ứng dụng trên lưới

Mức độ: Nâng cao

BFS và DFS là hai cách đi qua mọi đỉnh của đồ thị. Trong đề thi, đồ thị thường không được cho sẵn dưới dạng danh sách cạnh mà ẩn trong một bảng ô vuông (mê cung, bản đồ), một bàn cờ, hay một tập trạng thái. Bài này luyện cách nhìn ra đồ thị và chọn đúng cách duyệt.

BFS cho đường đi ngắn nhất

BFS đi từ đỉnh xuất phát ra xa dần theo từng lớp: lớp 0 là đỉnh xuất phát, lớp 1 là các đỉnh kề nó, lớp 2 là các đỉnh kề lớp 1 mà chưa thăm… Vì đi theo lớp, lần đầu tiên chạm tới một đỉnh chính là theo đường ít bước nhất. Khi mỗi bước đi có chi phí như nhau, BFS cho đường đi ngắn nhất.

Trên lưới, mỗi ô là một đỉnh, nối với các ô chung cạnh không phải tường. Mê cung (S xuất phát, T đích, # tường):

S . . #
# # . #
. . . T

Lớp	Các ô (hàng, cột)
0	(0, 0)
1	(0, 1)
2	(0, 2)
3	(1, 2)
4	(2, 2)
5	(2, 1), (2, 3) là T

Đích nằm ở lớp 5.

Python

import sys
from collections import deque
du_lieu = sys.stdin.read().split()
h, w = int(du_lieu[0]), int(du_lieu[1])
g = du_lieu[2:2 + h]
for r in range(h):
    for c in range(w):
        if g[r][c] == 'S':
            sr, sc = r, c
kc = [[-1] * w for _ in range(h)]       # -1: chưa thăm
kc[sr][sc] = 0
hang_doi = deque([(sr, sc)])
dap_so = -1
while hang_doi:
    r, c = hang_doi.popleft()
    if g[r][c] == 'T':
        dap_so = kc[r][c]
        break
    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 g[nr][nc] != '#' and kc[nr][nc] < 0:
            kc[nr][nc] = kc[r][c] + 1
            hang_doi.append((nr, nc))
print(dap_so)

C++

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

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (auto &s : g) cin >> s;
    int sr = 0, sc = 0;
    for (int r = 0; r < h; r++)
        for (int c = 0; c < w; c++)
            if (g[r][c] == 'S') sr = r, sc = c;
    vector<vector<int>> kc(h, vector<int>(w, -1));     // -1: chưa thăm
    kc[sr][sc] = 0;
    queue<pair<int, int>> hangDoi;
    hangDoi.push({sr, sc});
    int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1}, dapSo = -1;
    while (!hangDoi.empty()) {
        auto [r, c] = hangDoi.front();
        hangDoi.pop();
        if (g[r][c] == 'T') {
            dapSo = kc[r][c];
            break;
        }
        for (int t = 0; t < 4; t++) {
            int nr = r + dr[t], nc = c + dc[t];
            if (nr >= 0 && nr < h && nc >= 0 && nc < w && g[nr][nc] != '#' && kc[nr][nc] < 0) {
                kc[nr][nc] = kc[r][c] + 1;
                hangDoi.push({nr, nc});
            }
        }
    }
    cout << dapSo << "\n";
    return 0;
}

Lưu ý: đánh dấu đã thăm ngay khi đưa vào hàng đợi, không đợi lúc lấy ra. Đợi lúc lấy ra thì một ô có thể bị đưa vào hàng đợi nhiều lần, chương trình chậm đi nhiều.

BFS nhiều nguồn

Câu hỏi “mỗi ô cách nguồn gần nhất bao xa” (nguồn lửa, trạm phát sóng…): đưa tất cả nguồn vào hàng đợi từ đầu với khoảng cách 0, rồi BFS như thường. Kết quả giống như chạy BFS riêng từ từng nguồn rồi lấy nhỏ nhất, nhưng chỉ tốn một lần.

BFS trên trạng thái

Khi đường đi phụ thuộc vào thêm thông tin (đã phá bao nhiêu bức tường, đang cầm chìa khóa nào), trạng thái gồm cả vị trí và thông tin đó. Mỗi trạng thái là một đỉnh, BFS trên các trạng thái. Ví dụ được phá tối đa k bức tường: trạng thái là (hàng, cột, số tường đã phá), có h × w × (k + 1) trạng thái.

DFS và những gì nó trả lời được

DFS đi sâu theo một nhánh đến hết rồi mới quay lại. DFS không cho đường đi ngắn nhất, nhưng trả lời tốt các câu hỏi về cấu trúc: các vùng liên thông, có chu trình không, có phải đồ thị hai phía không (tô hai màu xen kẽ, gặp cạnh nối hai đỉnh cùng màu là không phải).

Trong Python, DFS đệ quy trên đồ thị 10⁵ đỉnh dễ vượt giới hạn đệ quy. Viết DFS bằng ngăn xếp thay cho đệ quy, hoặc dùng BFS khi thứ tự duyệt không quan trọng (đếm vùng, tô màu).

Luyện tập

Gồm 15 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. BFS trên lưới

Bài 1. Thoát mê cung

Mê cung là bảng h hàng, w cột gồm . (đi được), # (tường), S (xuất phát), T (đích), mỗi loại S, T có đúng một ô. Mỗi bước đi sang ô chung cạnh. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là mê cung. In ra số bước ít nhất từ S tới T, hoặc -1.

Ví dụ:

Nhập	In ra
3 4 S..# ##.# ...T	5

Kiểm tra: nhập

6 8
S.#.....
..#.##.#
#...#..#
.##.#.#.
.#..#...
...##.#T

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm phòng

Bản vẽ ngôi nhà là bảng h hàng, w cột gồm . (sàn) và # (tường). Các ô sàn chung cạnh thuộc cùng một phòng. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là bản vẽ. In ra số phòng và diện tích (số ô) của phòng lớn nhất, cách nhau dấu cách (không có phòng nào thì in 0 0).

Ví dụ:

Nhập	In ra
4 6 #.##.. #..#.# ####.. ..#.#.	4 6

Kiểm tra: nhập

6 8
........
.######.
.#....#.
.#.##.#.
.#....#.
.######.

Xem đáp số

2 18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Lửa lan

Khu rừng là bảng h hàng, w cột gồm F (đang cháy), . (cây), # (đá, không cháy). Mỗi phút, lửa lan từ ô đang cháy sang các ô cây chung cạnh. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là bản đồ. In ra số phút để mọi ô cây đều cháy, hoặc -1 nếu có ô cây không bao giờ cháy.

Ví dụ:

Nhập	In ra
3 4 F... .#.. ...F	2

Kiểm tra: nhập

5 7
.......
.##.##.
.#F..#.
.##.##.
.......

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Chạy thoát khỏi đám cháy

Tòa nhà là bảng h hàng, w cột gồm . (lối đi), # (tường), F (đang cháy, có thể nhiều ô), J (vị trí của Joe, đúng một ô). Mỗi phút Joe đi sang một ô chung cạnh, đồng thời lửa lan sang mọi ô lối đi chung cạnh với ô cháy. Joe không được bước vào ô đã cháy hoặc cháy cùng lúc Joe bước tới. Joe thoát khi bước ra ngoài bảng từ một ô ở biên. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là bản đồ. In ra số phút ít nhất để Joe thoát (tính cả bước ra ngoài), hoặc -1.

Ví dụ:

Nhập	In ra
4 4 #### #JF# #..# #..#	3

Kiểm tra: nhập

5 6
######
#J...#
#.##.F
#....#
###.##

Xem đáp số

-1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Hồ nước giữa đảo

Bản đồ là bảng h hàng, w cột gồm # (đất) và . (nước). Một vùng nước (các ô nước chung cạnh) là hồ nếu nó không chạm biên của bảng. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là bản đồ. In ra tổng số ô nước thuộc các hồ.

Ví dụ:

Nhập	In ra
5 5 ##### #..## #.#.# ##..# .####	6

Kiểm tra: nhập

6 7
#######
#..#..#
#.##..#
####.##
..#..##
#######

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. BFS trên trạng thái

Bài 6. Quân mã

Bàn cờ n × n. Quân mã đi theo hình chữ L (2 ô theo một hướng và 1 ô theo hướng vuông góc). Dòng duy nhất có n, r₁, c₁, r₂, c₂ (1 ≤ n ≤ 1000, ô đánh số từ 1). In ra số nước đi ít nhất để quân mã đi từ (r₁, c₁) tới (r₂, c₂), hoặc -1 nếu không tới được.

Ví dụ: nhập 8 1 1 8 8 thì in ra 6.

Kiểm tra: nhập 100 3 7 98 2.

Xem đáp số

48

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Thang máy kỳ lạ

Tòa nhà có f tầng (1 đến f). Thang máy chỉ có hai nút: lên đúng u tầng, xuống đúng d tầng (không đi được nếu vượt quá tầng f hoặc xuống dưới tầng 1). Dòng duy nhất có f, s, g, u, d (1 ≤ s, g ≤ f ≤ 10⁶, 0 ≤ u, d ≤ 10⁶). In ra số lần bấm nút ít nhất để từ tầng s tới tầng g, hoặc -1.

Ví dụ: nhập 10 1 10 2 1 thì in ra 6.

Kiểm tra: nhập 100 37 11 7 13.

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Biến số

Bắt đầu từ số a. Mỗi bước được nhân đôi số hiện tại hoặc trừ đi 1. Dòng duy nhất có a, b (1 ≤ a, b ≤ 10⁵). In ra số bước ít nhất để biến a thành b, với điều kiện số trong mọi bước nằm trong khoảng từ 1 đến 2 × 10⁵.

Ví dụ: nhập 4 6 thì in ra 2.

Kiểm tra: nhập 3 100000.

Xem đáp số

24

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Phá tường

Mê cung h hàng, w cột gồm . (đi được) và # (tường); xuất phát ở ô trên cùng bên trái, đích ở ô dưới cùng bên phải (cả hai ô đều là .). Được phá tối đa k bức tường (đi vào ô # coi như phá nó). Dòng đầu có h, w, k (1 ≤ h, w ≤ 300, 0 ≤ k ≤ 5), h dòng sau là mê cung. In ra số bước ít nhất, hoặc -1.

Ví dụ:

Nhập	In ra
3 4 1 .#.. .##. ..#.	5

Kiểm tra: nhập

5 6 2
.#....
.#.##.
.#.#..
##.#.#
...#..

Xem đáp số

9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Chìa khóa và cửa

Mê cung h hàng, w cột gồm . (đi được), # (tường), S (xuất phát), T (đích), chữ thường a đến d (chìa khóa) và chữ hoa A đến D (cửa). Đi qua ô có chìa thì nhặt được chìa đó (giữ mãi); chỉ đi vào được ô cửa X khi đang có chìa x tương ứng. Dòng đầu có h, w (1 ≤ h, w ≤ 100), h dòng sau là mê cung. In ra số bước ít nhất từ S tới T, hoặc -1.

Ví dụ:

Nhập	In ra
3 5 Sa.A. ###.. T.B.b	10

Kiểm tra: nhập

5 6
S.#..T
..#.D.
a.C.#.
#.##.#
c...#d

Xem đáp số

15

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Cấu trúc đồ thị

Bài 11. Số nhóm bạn

Có n người và m cặp bạn. Bạn của bạn cùng nhóm. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra số nhóm và số người của nhóm đông nhất.

Ví dụ:

Nhập	In ra
6 4 1 2 2 3 4 5 6 6	3 3

Kiểm tra: nhập

10 7
1 5
5 9
2 2
3 4
4 8
8 3
10 6

Xem đáp số

5 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Chia hai đội đối đầu

Có n người và m cặp không thích nhau. Chia n người thành hai đội sao cho mỗi cặp không thích nhau ở hai đội khác nhau. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u khác v). In ra YES nếu chia được, ngược lại NO.

Ví dụ:

Nhập	In ra
4 4 1 2 2 3 3 4 4 1	YES

Kiểm tra: nhập

6 6
1 2
2 3
3 1
4 5
5 6
6 4

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Có vòng không

Đồ thị vô hướng n đỉnh, m cạnh (không có cạnh nối một đỉnh với chính nó, không có hai cạnh nối cùng hai đỉnh). Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra YES nếu đồ thị có chu trình, ngược lại NO.

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 4 5 2 4	YES

Kiểm tra: nhập

8 7
1 2
2 3
3 4
5 6
6 7
7 8
4 5

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đếm số đường đi ngắn nhất

Đồ thị vô hướng n đỉnh, m cạnh (mỗi cạnh dài 1). Dòng đầu có n, m (2 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v. In ra độ dài đường đi ngắn nhất từ đỉnh 1 tới đỉnh n và số đường đi ngắn nhất như vậy (chia lấy dư 10⁹ + 7), cách nhau dấu cách. Nếu không tới được thì in -1 0.

Ví dụ:

Nhập	In ra
4 5 1 2 1 3 2 4 3 4 2 3	2 2

Kiểm tra: nhập

7 10
1 2
1 3
1 4
2 5
3 5
4 6
5 7
6 7
3 6
2 3

Xem đáp số

3 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Khoảng cách từ đỉnh 1 tới mọi đỉnh

Đồ thị có hướng n đỉnh, m cạnh (mỗi cạnh dài 1). Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v: cạnh một chiều từ u tới v. In ra khoảng cách ngắn nhất từ đỉnh 1 tới các đỉnh 1, 2, …, n (-1 nếu không tới được).

Ví dụ:

Nhập	In ra
5 5 1 2 2 3 3 1 1 4 5 4	0 1 2 1 -1

Kiểm tra: nhập

8 9
1 2
2 3
3 4
4 1
2 5
5 6
6 2
7 8
6 8

Xem đáp số

0 1 2 3 2 3 -1 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.