Wiki › Thuật toán › Thuật toán đồ thị › BFS (Tìm kiếm theo chiều rộng)

BFS (Tìm kiếm theo chiều rộng)

huunguyen Updated Tháng 9. 30, 2026 Đọc 20 phút 3 lượt xem

BFS (Breadth-First Search, tìm kiếm theo chiều rộng) là thuật toán duyệt đồ thị theo từng lớp khoảng cách tính từ đỉnh xuất phát. Trên đồ thị không trọng số (mỗi cạnh dài 1), BFS cho ngay đường đi ngắn nhất từ một đỉnh tới mọi đỉnh khác trong $O (V + E)$ , thay vì phải thử mọi đường đi (số đường có thể tăng theo hàm mũ). Cùng một khung code, BFS giải được đường đi ngắn nhất trên lưới, khoảng cách tới nguồn gần nhất (BFS đa nguồn), số bước tối thiểu trong các trò chơi / câu đố (BFS trên không gian trạng thái) và số đường đi ngắn nhất.

Ý tưởng / Trực giác

Hãy tưởng tượng thả một viên đá xuống mặt nước ở đỉnh $s$ : sóng lan ra thành từng vòng. Vòng 0 là $s$ , vòng 1 là các đỉnh kề $s$ , vòng 2 là các đỉnh kề vòng 1 mà chưa bị chạm tới, ... Đỉnh $v$ nằm ở vòng $k$ đúng khi đường đi ngắn nhất từ $s$ tới $v$ có $k$ cạnh.

BFS hiện thực "sóng lan" này bằng một hàng đợi FIFO (vào trước ra trước):

Đưa $s$ vào hàng đợi, $d i s t [s] = 0$ .
Lấy đỉnh $u$ ở đầu hàng đợi; với mỗi đỉnh kề $v$ chưa được phát hiện, gán $d i s t [v] = d i s t [u] + 1$ , ghi nhớ $p a r [v] = u$ và đưa $v$ vào cuối hàng đợi.
Lặp tới khi hàng đợi rỗng.

Vì sao đúng? Bất biến then chốt: tại mọi thời điểm, hàng đợi chỉ chứa các đỉnh có khoảng cách $d$ rồi tới các đỉnh có khoảng cách $d + 1$ , theo đúng thứ tự đó. Lý do: ta chỉ lấy ra đỉnh ở lớp $d$ và chỉ đẩy vào đỉnh ở lớp $d + 1$ (đẩy vào cuối). Hệ quả:

Các đỉnh được lấy ra theo thứ tự khoảng cách không giảm: toàn bộ lớp 0, rồi toàn bộ lớp 1, rồi lớp 2, ...
Lần đầu tiên $v$ được phát hiện là từ một đỉnh $u$ có $d i s t [u]$ nhỏ nhất trong các láng giềng của $v$ . Mọi đường đi tới $v$ phải đi qua một láng giềng nào đó, nên $d i s t [u] + 1$ chính là khoảng cách ngắn nhất. Vì vậy gán một lần là xong, không bao giờ phải sửa lại.

Tính chất "gán một lần là xong" chỉ đúng vì mọi cạnh dài bằng nhau. Khi cạnh có trọng số khác nhau, một đường nhiều cạnh có thể ngắn hơn đường ít cạnh, bất biến trên sụp đổ; khi đó cần 0-1 BFS (trọng số 0/1) hoặc Dijkstra (trọng số không âm bất kỳ).

Ví dụ chạy tay

Đồ thị vô hướng 6 đỉnh, xuất phát từ $s = 1$ :

        1
       / \
      2   3
       \ / \
        4   5
         \ /
          6

Danh sách kề: 1:[2,3]  2:[1,4]  3:[1,4,5]  4:[2,3,6]  5:[3,6]  6:[4,5]

Ký hiệu v(d) là đỉnh $v$ trong hàng đợi kèm $d i s t [v]$ .

Khởi tạo: dist[1]=0            hàng đợi = [ 1(0) ]

Lấy 1 (d=0): 2 mới -> dist=1, par=1
             3 mới -> dist=1, par=1
                               hàng đợi = [ 2(1) 3(1) ]

Lấy 2 (d=1): 1 đã thấy, bỏ qua
             4 mới -> dist=2, par=2
                               hàng đợi = [ 3(1) 4(2) ]       <- lớp 1 rồi lớp 2

Lấy 3 (d=1): 1, 4 đã thấy, bỏ qua (4 KHÔNG bị sửa par)
             5 mới -> dist=2, par=3
                               hàng đợi = [ 4(2) 5(2) ]

Lấy 4 (d=2): 2, 3 đã thấy
             6 mới -> dist=3, par=4
                               hàng đợi = [ 5(2) 6(3) ]

Lấy 5 (d=2): 3, 6 đã thấy      hàng đợi = [ 6(3) ]
Lấy 6 (d=3): 4, 5 đã thấy      hàng đợi = [ ]   -> kết thúc

Kết quả chia thành các lớp:

đỉnh :  1   2   3   4   5   6
dist :  0   1   1   2   2   3
par  :  -   1   1   2   3   4

lớp 0: {1}   lớp 1: {2, 3}   lớp 2: {4, 5}   lớp 3: {6}

Quan sát hàng đợi ở mọi bước: khoảng cách trong đó luôn có dạng d d ... d d+1 ... d+1, đúng bất biến ở trên.

Truy vết đường đi tới đỉnh 6: đi ngược theo par từ đích về nguồn rồi đảo lại.

6 --par--> 4 --par--> 2 --par--> 1        đảo ngược:  1 -> 2 -> 4 -> 6   (3 cạnh)

Cài đặt

BFS cơ bản + truy vết đường đi

Đọc đồ thị vô hướng $n$ đỉnh, $m$ cạnh; in độ dài và một đường đi ngắn nhất từ $1$ tới $n$ (hoặc $- 1$ nếu không tới được).

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int s = 1, t = n;
    vector<int> dist(n + 1, -1), par(n + 1, 0);   // -1 = not discovered yet
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] != -1) continue;   // already discovered: dist[v] is final
            dist[v] = dist[u] + 1;         // mark when PUSHING, not when popping
            par[v] = u;
            q.push(v);
        }
    }

    if (dist[t] == -1) { cout << -1 << '\n'; return 0; }

    vector<int> path;
    for (int v = t; v != s; v = par[v]) path.push_back(v);  // walk back to source
    path.push_back(s);
    reverse(path.begin(), path.end());

    cout << dist[t] << '\n';
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

Phiên bản Python (dùng collections.deque; không dùng list.pop(0) vì thao tác đó là $O (n)$ ):

from collections import deque

def bfs(adj, s):
    n = len(adj)
    dist = [-1] * n
    par = [-1] * n
    dist[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                par[v] = u
                q.append(v)
    return dist, par

def get_path(dist, par, s, t):
    if dist[t] == -1:
        return []          # t is unreachable from s
    path = [t]
    while path[-1] != s:
        path.append(par[path[-1]])
    return path[::-1]

BFS trên lưới (4 hoặc 8 hướng, ô cấm)

Trên lưới, mỗi ô là một đỉnh, cạnh nối các ô kề nhau; không cần dựng danh sách kề mà sinh láng giềng bằng mảng hướng DR, DC.

#include <bits/stdc++.h>
using namespace std;

// 4 directions: up, down, left, right
const int DR4[] = {-1, 1, 0, 0}, DC4[] = {0, 0, -1, 1};
// 8 directions (king moves): use these arrays with d < 8 instead
// const int DR8[] = {-1,-1,-1, 0, 0, 1, 1, 1}, DC8[] = {-1, 0, 1,-1, 1,-1, 0, 1};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);             // '.' free, '#' blocked, 'S' start, 'T' target
    for (auto& row : g) cin >> row;

    int sr = -1, sc = -1, tr = -1, tc = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S') sr = i, sc = j;
            if (g[i][j] == 'T') tr = i, tc = j;
        }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + DR4[d], nc = c + DC4[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;   // check bounds FIRST
            if (g[nr][nc] == '#' || dist[nr][nc] != -1) continue;   // blocked or seen
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    cout << dist[tr][tc] << '\n';    // -1 if unreachable
}

Muốn truy vết trên lưới, lưu par là hướng đã đi vào ô (một số $0 . .3$ ) hoặc chỉ số ô cha pr * m + pc, rồi đi ngược như trường hợp đồ thị.

BFS đa nguồn (multi-source BFS)

Bài toán: với mỗi đỉnh, tìm khoảng cách tới nguồn gần nhất trong một tập nguồn (lửa lan từ nhiều đám cháy, khoảng cách tới cửa hàng gần nhất, ...). Chạy BFS riêng từ từng nguồn tốn $O (k (V + E))$ . Cách đúng: đưa tất cả nguồn vào hàng đợi ở lớp 0 ngay từ đầu, rồi chạy BFS một lần.

Vì sao đúng: tưởng tượng thêm một "siêu nguồn" ảo $S^{*}$ nối tới mọi nguồn thật bằng cạnh dài 1, rồi chạy BFS thường từ $S^{*}$ . Sau khi lấy $S^{*}$ ra khỏi hàng đợi, hàng đợi chứa đúng tất cả các nguồn thật ở lớp 1, và từ đó BFS chạy y hệt BFS đa nguồn. Mọi đường đi từ $S^{*}$ tới $v$ đều có dạng $S^{*} \to s_{i} \to \dots \to v$ , nên khoảng cách từ $S^{*}$ tới $v$ bằng $1 + {min}_{i} d (s_{i}, v)$ ; trừ đi 1 là ra khoảng cách tới nguồn gần nhất. Việc "đặt mọi nguồn vào lớp 0 ngay từ đầu" chính là bỏ qua bước lấy $S^{*}$ ra và dịch mọi khoảng cách xuống 1.

// dist[v] = distance from v to the NEAREST source
vector<int> multiSourceBfs(const vector<vector<int>>& adj, const vector<int>& sources) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    for (int s : sources)
        if (dist[s] == -1) { dist[s] = 0; q.push(s); }   // all sources on layer 0
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    return dist;
}

Ví dụ trên lưới $3 \times 5$ với hai nguồn S ở $(0, 0)$ và $(1, 4)$ , # là ô cấm:

Lưới:              Khoảng cách tới S gần nhất:
S . # . .          0 1 # 2 1
. . # . S          1 2 # 1 0
. . . . .          2 3 3 2 1
                       ^
                  ô (2,2): từ S trái cần 4 bước, từ S phải cần 3 bước -> 3

Hai "làn sóng" lan đồng thời và gặp nhau ở giữa; ô nào bị sóng chạm trước thì thuộc về nguồn đó.

BFS trên không gian trạng thái

Nhiều bài không cho đồ thị tường minh mà cho luật chuyển trạng thái: "mỗi bước được làm một thao tác, hỏi số bước ít nhất". Khi đó:

Đỉnh = một trạng thái đầy đủ, đủ để biết mọi nước đi tiếp theo, ví dụ $(hàng, cột, hướng)$ , $(ô, tập chìa khóa đang giữ)$ , $(ô, số lần rẽ đã dùng)$ .
Cạnh = một thao tác hợp lệ, tốn 1 bước.
Mã hóa trạng thái thành một số nguyên để dùng mảng dist thay cho map: với trạng thái $(r, c, x)$ trong đó $x \in [0, X)$ , dùng $i d = (r \cdot m + c) \cdot X + x$ ; giải mã ngược bằng % và /.

Ví dụ: lưới có chìa khóa a..f và cửa A..F (chỉ đi qua cửa A khi đã nhặt chìa a). Vị trí thôi là chưa đủ, vì cùng một ô nhưng cầm chìa khác nhau thì đi tiếp khác nhau; trạng thái là $(r, c, m a s k)$ với $m a s k$ là tập chìa đã nhặt ( $2^{6} = 64$ giá trị).

#include <bits/stdc++.h>
using namespace std;

// Grid: '.', '#', 'S', 'T', keys 'a'..'f', doors 'A'..'F'.
// State = (row, col, mask of keys held), encoded as one int.
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto& row : g) cin >> row;

    const int K = 6, MASKS = 1 << K;
    auto id = [&](int r, int c, int mask) { return (r * m + c) * MASKS + mask; };

    vector<int> dist(n * m * MASKS, -1);
    queue<int> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'S') { dist[id(i, j, 0)] = 0; q.push(id(i, j, 0)); }

    const int DR[] = {-1, 1, 0, 0}, DC[] = {0, 0, -1, 1};
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        int mask = cur % MASKS, cell = cur / MASKS;   // decode state
        int r = cell / m, c = cell % m;
        if (g[r][c] == 'T') { cout << dist[cur] << '\n'; return 0; }  // first pop = shortest

        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            char ch = g[nr][nc];
            if (ch == '#') continue;
            if (ch >= 'A' && ch <= 'F' && !(mask >> (ch - 'A') & 1)) continue;  // locked door
            int nmask = mask;
            if (ch >= 'a' && ch <= 'f') nmask |= 1 << (ch - 'a');              // pick up key
            int nxt = id(nr, nc, nmask);
            if (dist[nxt] != -1) continue;
            dist[nxt] = dist[cur] + 1;
            q.push(nxt);
        }
    }
    cout << -1 << '\n';
}

Trước khi code, luôn đếm số trạng thái và nhân với số phép chuyển: ở đây $n \cdot m \cdot 64$ trạng thái, mỗi trạng thái 4 phép chuyển. Với $n = m = 100$ là khoảng $6, 4 \cdot 10^{5}$ trạng thái, rất nhẹ; với $n = m = 1000$ thì $6, 4 \cdot 10^{7}$ số int (256 MB) là quá lớn, phải rút gọn trạng thái.

Đếm số đường đi ngắn nhất

Gọi $c n t [v]$ là số đường đi ngắn nhất từ $s$ tới $v$ . Mọi đường đi ngắn nhất tới $v$ đi qua đúng một đỉnh "trước" $u$ với $d i s t [u] = d i s t [v] - 1$ và cạnh $u \to v$ , nên:

$c n t [v] = \sum_{u \to v, d i s t [u] = d i s t [v] - 1} c n t [u] .$

BFS lấy đỉnh ra theo từng lớp, nên khi $u$ được lấy ra thì mọi đỉnh ở lớp $d i s t [u] - 1$ đã được xử lý xong, tức $c n t [u]$ đã đủ. Chỉ cần sửa BFS: khi gặp $v$ đã thấy mà $d i s t [v] = d i s t [u] + 1$ thì vẫn cộng dồn.

const long long MOD = 1e9 + 7;

// cnt[v] = number of shortest paths from s to v (mod MOD), 0 if unreachable.
// Vertices are indexed 0..adj.size()-1 (1-indexed graphs just leave index 0 unused).
vector<long long> countShortestPaths(const vector<vector<int>>& adj, int s) {
    int V = adj.size();
    vector<int> dist(V, -1);
    vector<long long> cnt(V, 0);
    queue<int> q;
    dist[s] = 0; cnt[s] = 1; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {                     // first discovery: next layer
                dist[v] = dist[u] + 1;
                cnt[v] = cnt[u];
                q.push(v);
            } else if (dist[v] == dist[u] + 1) {     // another shortest predecessor
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }
        }
    }
    return cnt;
}

Chạy trên đồ thị ví dụ ở trên:

Đỉnh	dist	Các đỉnh "trước"	cnt
1	0	(nguồn)	1
2	1	1	1
3	1	1	1
4	2	2, 3	1 + 1 = 2
5	2	3	1
6	3	4, 5	2 + 1 = 3

Ba đường ngắn nhất tới 6 là $1 - 2 - 4 - 6$ , $1 - 3 - 4 - 6$ , $1 - 3 - 5 - 6$ .

Độ phức tạp

Thời gian $O (V + E)$ . Mỗi đỉnh được đưa vào hàng đợi đúng một lần (vì bị đánh dấu ngay khi đẩy vào), nên lấy ra một lần; khi lấy $u$ ra ta duyệt $\deg (u)$ cạnh, tổng các bậc là $2 E$ (vô hướng) hoặc $E$ (có hướng). Phần đếm đường đi chỉ thêm $O (1)$ mỗi cạnh nên vẫn $O (V + E)$ .
Bộ nhớ $O (V + E)$ : danh sách kề $O (V + E)$ , các mảng dist, par, cnt và hàng đợi $O (V)$ .
Lưới $n \times m$ : $V = n m$ , mỗi ô có $4$ (hoặc $8$ ) láng giềng, nên $O (n m)$ cả thời gian lẫn bộ nhớ.
Không gian trạng thái: $O (S \cdot T)$ thời gian và $O (S)$ bộ nhớ, với $S$ là số trạng thái và $T$ là số phép chuyển từ một trạng thái. Luôn ước lượng $S$ trước khi cài.
Đa nguồn: vẫn $O (V + E)$ cho mọi nguồn cùng lúc, thay vì $O (k (V + E))$ khi chạy $k$ lần.

⚠️ Lỗi thường gặp

Đánh dấu khi lấy ra thay vì khi đẩy vào. Nếu chỉ gán visited[u] = true lúc pop, một đỉnh có thể bị đẩy vào hàng đợi nhiều lần (mỗi láng giềng đẩy một lần). Kết quả khoảng cách có thể vẫn đúng nhưng hàng đợi phình tới $O (E)$ phần tử, trên lưới $1000 \times 1000$ dễ TLE/MLE; với bài đếm đường đi thì còn đếm sai. Cách tránh: gán dist[v] ngay khi phát hiện và đẩy vào.
Dùng $0$ làm giá trị "chưa thăm". Nguồn có $d i s t = 0$ nên sẽ bị coi là chưa thăm và bị thăm lại. Khởi tạo dist = -1 (hoặc dùng mảng visited riêng).
Dùng DFS để tìm đường ngắn nhất. DFS đi sâu theo một nhánh, lần đầu chạm tới $v$ không phải đường ngắn nhất. Đường ngắn nhất trên đồ thị không trọng số phải dùng BFS.
Truy cập ngoài lưới. Viết if (g[nr][nc] == '#' || nr < 0 ...) là truy cập trước rồi mới kiểm tra, gây lỗi bộ nhớ. Luôn kiểm tra biên trước. Cũng cẩn thận nhầm (hàng, cột) với $(x, y)$ và nhầm 4 hướng với 8 hướng so với đề.
Đa nguồn nhưng chạy BFS lần lượt từng nguồn. Vừa chậm ( $O (k (V + E))$ ), vừa sai nếu dùng chung mảng dist mà không cập nhật lại: đỉnh bị nguồn xét trước "chiếm" mất dù nguồn sau gần hơn. Đưa tất cả nguồn vào hàng đợi với khoảng cách 0 trước khi bắt đầu vòng lặp.
Đếm đường đi: tràn số và cạnh lặp. Số đường ngắn nhất có thể cỡ $2^{V / 2}$ , phải lấy modulo hoặc chặn trên (ví dụ chỉ cần biết $0$ , $1$ hay $\geq 2$ thì lưu $min (c n t, 2)$ ). Nếu đề nói hai cạnh trùng nhau là cùng một kết nối thì phải bỏ cạnh trùng trước, nếu không một đường sẽ bị đếm hai lần.
Thiếu chiều trạng thái. Trong bài có hướng đi, số lần rẽ, chìa khóa, ... mà chỉ lưu dist[r][c] thì BFS sẽ "chặn" một trạng thái tốt chỉ vì cùng ô đã được thăm bằng trạng thái khác. Tự hỏi: hai lần đứng ở cùng ô này có luôn đi tiếp giống nhau không? Nếu không, trạng thái còn thiếu.
Bùng nổ trạng thái / dùng map để lưu dist. Mã hóa trạng thái thành số nguyên và dùng vector; map<tuple<...>, int> thêm thừa số $\log$ và hằng số lớn. Ước lượng $S$ trước, nếu quá lớn thì tìm cách rút gọn trạng thái.
Truy vết: quên đảo ngược hoặc đích không tới được. Đi theo par cho đường từ đích về nguồn, phải reverse. Kiểm tra dist[t] == -1 trước khi truy vết để khỏi lặp vô hạn.
Áp dụng BFS khi cạnh có trọng số khác nhau. BFS chỉ đúng khi mọi cạnh cùng độ dài. Trọng số ${0, 1}$ dùng 0-1 BFS, trọng số không âm bất kỳ dùng Dijkstra.

Biến thể / Mở rộng

0-1 BFS: cạnh trọng số 0 hoặc 1, thay queue bằng deque (trọng số 0 đẩy đầu, 1 đẩy cuối), vẫn $O (V + E)$ .
Dijkstra: trọng số không âm tổng quát, thay hàng đợi bằng hàng đợi ưu tiên. BFS chính là Dijkstra khi mọi cạnh bằng 1 (hàng đợi FIFO đã tự sắp theo khoảng cách).
BFS ngược từ đích: khi có nhiều điểm xuất phát nhưng chỉ một đích (hoặc muốn biết khoảng cách từ mọi ô tới đích), BFS một lần từ đích trên đồ thị ngược thay vì BFS từ từng điểm xuất phát.
BFS theo lớp (level-by-level): xử lý trọn một lớp rồi mới sang lớp sau, hữu ích khi cần làm gì đó "sau mỗi bước thời gian" hoặc khi biểu diễn cả lớp bằng bitset để tăng tốc.
BFS hai chiều (bidirectional BFS): loang đồng thời từ nguồn và đích, dừng khi hai làn sóng gặp nhau; giảm mạnh số trạng thái khi không gian trạng thái phân nhánh lớn.
Kiểm tra đồ thị hai phía: tô màu theo tính chẵn lẻ của $d i s t$ ; có cạnh nối hai đỉnh cùng lớp chẵn lẻ thì đồ thị không hai phía.

Bài tập luyện

Luyện kỹ thuật

Đội xô nước (buckets19) (Sơ cấp) Khởi động: BFS trên lưới $10 \times 10$ có ô cấm, đáp án là độ dài đường ngắn nhất trừ 1.
Cõng Bạn (piggyback) (Nghiệp dư) Chạy BFS từ ba đỉnh khác nhau (hai điểm xuất phát và đích) rồi thử mọi điểm gặp nhau; luyện dùng lại hàm BFS và mảng dist.
Field Day (fieldday) (Trung cấp) BFS đa nguồn trên không gian trạng thái $2^{C}$ mặt nạ bit (mỗi bước lật một bit), kết hợp mẹo lấy phần bù để biến "khác nhiều nhất" thành "gần nhất".
Khu rừng Biridian (mikemon) (Nâng cao) BFS ngược từ cửa ra trên lưới $1000 \times 1000$ : đối thủ chặn được bạn khi khoảng cách của họ tới cửa ra không lớn hơn của bạn.
Đường tới chỗ làm (igorwork) (Nâng cao) BFS trên không gian trạng thái $(ô, hướng, số lần rẽ)$ ; ví dụ điển hình của việc "vị trí thôi là chưa đủ".

Đề VOI

Bộ sưu tập (voi05_coll) (Trung cấp) VOI 2005: BFS trên không gian trạng thái chỉ gồm $5^{3} = 125$ bộ tiền, mỗi quy tắc đổi là một cạnh; lưu ý bộ có giá trị là điểm dừng, không mở rộng tiếp.
Quân tượng (voi06_bishop) (Trung cấp) VOI 2006: BFS trên các ô bàn cờ, mỗi nước trượt dọc 4 đường chéo tới khi gặp quân cờ hoặc mép, không được dừng trượt ở ô đã thăm.
Ổn định (voi10_stable) (Trung cấp) VOI 2010: đếm số đường đi ngắn nhất bằng BFS nhưng chỉ cần chặn ở mức "ít nhất 2"; nhớ bỏ các bản ghi cạnh trùng.
Người đặc biệt (voi18_spone) (Trung cấp) VOI 2018: không phải đường đi ngắn nhất mà là lan truyền bằng hàng đợi đa nguồn từ tập người đặc biệt ban đầu, một đỉnh vào hàng đợi khi đủ $K$ láng giềng khác nhau đã đặc biệt.
Robocon (voi12_rbcon) (Nâng cao) VOI 2012: hai Robot không được đứng yên nên phải loang theo từng lớp thời gian tập ô mỗi Robot có thể đứng, dừng ở lớp đầu tiên hai tập giao nhau (có thể tăng tốc bằng bitset).
Trò chơi khối hộp (voi18_blgame) (Kỳ cựu) VOI 2018: BFS trên trạng thái $(ô góc, hướng khối hộp)$ với 8 phép đẩy/lật, kiểm tra mỗi vị trí trong $O (1)$ bằng tổng tiền tố.
Thu nhập ổn định (voi23_income) (Kỳ cựu) VOI 2023: quy về khoảng cách tới đỉnh có giá trị lớn nhất đi tới được, tính bằng BFS đa nguồn trên đồ thị ngược theo thứ tự giá trị giảm dần; cạnh là cả một đoạn nên cần cấu trúc dữ liệu để lấy đỉnh chưa thăm.
Trại bò tót (voi16_rbull) (Kỳ cựu) VOI 2016: bán kính hình thoi lớn nhất tại mỗi tâm $p$ là $min$ (khoảng cách từ $p$ tới biên, khoảng cách từ $p$ tới "cọc xấu" gần nhất), trong đó khoảng cách tới cọc xấu gần nhất tính bằng BFS đa nguồn trên lưới, rồi đếm cọc bằng tổng tiền tố trên lưới xoay.
Dãy đèn (voi26_light) (Chuyên gia) VOI 2026: mã hóa đoạn đèn thành bộ đếm $(c_{0}, c_{1}, c_{2})$ , chặn số bóng tắt ở một ngưỡng nhỏ để số trạng thái hữu hạn, và BFS ngược một lần từ trạng thái "tất cả tắt" để trả lời mọi truy vấn trong $O (1)$ .

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.