0-1 BFS

0-1 BFS là thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số cạnh chỉ gồm 0 hoặc 1. Nó cho kết quả như Dijkstra nhưng chạy trong $O(V+E)$ thay vì $O((V+E)\log V)$, nhờ thay hàng đợi ưu tiên (priority queue) bằng một deque hai đầu. Đây là công cụ chuẩn cho các bài "đi trên lưới với một số bước miễn phí, một số bước tốn 1" hoặc "tối thiểu số lần phá tường / đổi hướng / đảo trạng thái".

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

Hãy nhớ lại vì sao BFS thường tìm được đường ngắn nhất khi mọi cạnh có trọng số 1: BFS lấy đỉnh ra theo đúng thứ tự khoảng cách tăng dần, và hàng đợi tại mọi thời điểm chỉ chứa các đỉnh có khoảng cách $d$ hoặc $d+1$ (chênh nhau tối đa 1). Nhờ đó đỉnh nào được lấy ra lần đầu thì đã đạt khoảng cách tối ưu.

Khi cạnh có trọng số $\in \{0,1\}$, tính chất "hàng đợi chỉ chứa hai mức kề nhau" vẫn có thể giữ được, nhưng ta phải cẩn thận với cạnh trọng số 0: đi qua nó không làm tăng khoảng cách, nên đỉnh mới phải được xử lý cùng mức với đỉnh hiện tại, tức phải đứng trước những đỉnh ở mức $d+1$ đang chờ.

Giải pháp là dùng deque và quy tắc:

• Cạnh trọng số 0 → push_front (đẩy vào đầu deque): đỉnh mới cùng khoảng cách với đỉnh hiện tại, cần xử lý ngay.
• Cạnh trọng số 1 → push_back (đẩy vào cuối deque): đỉnh mới ở khoảng cách lớn hơn 1, xử lý sau.

Bất biến (invariant) cốt lõi: deque luôn được sắp theo khoảng cách không giảm, và giá trị nhỏ nhất nằm ở đầu. Vì mọi cạnh chỉ là 0 hoặc 1, khoảng cách trong deque chỉ chênh nhau tối đa 1, nên việc chèn vào hai đầu là đủ để giữ thứ tự — không cần heap. Đây chính là phiên bản Dijkstra mà "priority queue" suy biến thành deque vì chỉ có hai mức ưu tiên.

Lưu ý quan trọng: một đỉnh có thể bị đẩy vào deque nhiều lần (mỗi lần tìm thấy khoảng cách tốt hơn). Vì vậy khi lấy đỉnh ra ta phải kiểm tra lại $dist$ để bỏ qua các bản cũ đã lỗi thời (xem phần Lỗi thường gặp).

Ví dụ chạy tay

Xét lưới $1\times 5$, di chuyển sang ô kề: ô trống . tốn 0, ô tường # tốn 1 (phải phá). Tìm số tường tối thiểu để đi từ ô 0 đến ô 4.

chỉ số:   0    1    2    3    4
lưới:    [.]  [#]  [.]  [#]  [.]
chi phí:  -    1    0    1    0     (chi phí khi BƯỚC VÀO ô đó)

Đặt $dist$ ban đầu là $\infty$, $dist[0]=0$, deque $=[0]$. Ký hiệu (d) là khoảng cách kèm theo mỗi phần tử trong deque.

Bước 1: lấy đầu = 0 (d=0). Hàng xóm 1: vào ô '#' tốn 1.
        dist[1] = 0+1 = 1. Cạnh trọng số 1 -> push_back.
        deque = [ 1(d=1) ]
        dist:  [0,  1,  ∞,  ∞,  ∞]

Bước 2: lấy đầu = 1 (d=1). Hàng xóm 0 (đã tối ưu, bỏ qua),
        hàng xóm 2: vào ô '.' tốn 0.
        dist[2] = 1+0 = 1. Cạnh trọng số 0 -> push_FRONT.
        deque = [ 2(d=1) ]          <- ô 2 chen lên ĐẦU vì cùng mức d=1
        dist:  [0,  1,  1,  ∞,  ∞]

Bước 3: lấy đầu = 2 (d=1). Hàng xóm 3: vào '#' tốn 1.
        dist[3] = 1+1 = 2. push_back.
        deque = [ 3(d=2) ]
        dist:  [0,  1,  1,  2,  ∞]

Bước 4: lấy đầu = 3 (d=2). Hàng xóm 4: vào '.' tốn 0.
        dist[4] = 2+0 = 2. push_FRONT.
        deque = [ 4(d=2) ]
        dist:  [0,  1,  1,  2,  2]

Bước 5: lấy đầu = 4 (d=2). Đích! dist[4] = 2.

Kết quả: cần phá 2 tường (ô 1 và ô 3). Quan sát then chốt ở bước 2 và 4: cạnh trọng số 0 khiến ô mới được push_front để xử lý trước mọi đỉnh ở mức cao hơn — đó là điều giữ cho khoảng cách lấy ra luôn không giảm.

Cài đặt

Phiên bản tổng quát cho đồ thị danh sách kề với trọng số 0/1:

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

// adj[u] = danh sách {v, w} với w ∈ {0, 1}
vector<int> bfs01(int src, int n, vector<vector<pair<int,int>>>& adj) {
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : adj[u]) {
            // Nếu đi qua u cho khoảng cách tốt hơn tới v thì cập nhật
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v); // trọng số 0: cùng mức -> đầu
                else        dq.push_back(v);  // trọng số 1: mức sau -> cuối
            }
        }
    }
    return dist;
}

Áp dụng cho lưới (phá tường tối thiểu)

Đây là dạng hay gặp nhất: không cần dựng danh sách kề tường minh, mà sinh hàng xóm trực tiếp từ ô.

// grid[i][j] = 0 (ô trống) hoặc 1 (ô tường, phải phá để bước vào)
int minObstacles(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    deque<pair<int,int>> dq;
    dist[0][0] = 0;
    dq.push_back({0, 0});

    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int w = grid[nx][ny];               // chi phí bước VÀO ô (nx, ny)
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) dq.push_front({nx, ny});
                else        dq.push_back({nx, ny});
            }
        }
    }
    return dist[n-1][m-1];
}

Mẹo mô hình hoá: cạnh trọng số 1 ẩn

Nhiều bài không cho sẵn trọng số 0/1 mà bạn phải tự đặt. Ví dụ "đổi chiều một cạnh có hướng tốn 1, giữ nguyên tốn 0":

// Với mỗi cạnh u -> v có sẵn:
adj[u].push_back({v, 0});  // đi đúng chiều: miễn phí
adj[v].push_back({u, 1});  // đi ngược chiều (phải đảo cạnh): tốn 1

Độ phức tạp

• Thời gian: $O(V+E)$. Mỗi cạnh chỉ gây ra tối đa một lần cải thiện khoảng cách của đỉnh đích, nên tổng số lần push bị chặn bởi $O(E)$. Mỗi đỉnh lấy ra khỏi deque được xử lý một lần thực sự (nhờ kiểm tra $dist$ lọc bản cũ), nên tổng công việc là $O(V+E)$ — không có thừa số $\log$ như Dijkstra vì deque chỉ tốn $O(1)$ cho mỗi thao tác hai đầu.
• Bộ nhớ: $O(V+E)$. Cần $O(V)$ cho mảng $dist$ và cho deque (một đỉnh có thể nằm trong deque nhiều bản, nhưng tổng số bản bị chặn bởi số lần push $\le E$), cộng $O(V+E)$ cho biểu diễn đồ thị. Với lưới $N\times M$, đây là $O(NM)$.

So sánh nhanh với các thuật toán họ hàng:

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

• Không kiểm tra lại $dist$ khi lấy đỉnh ra. Vì một đỉnh có thể bị đẩy vào deque nhiều lần với các khoảng cách khác nhau, bản cũ (lỗi thời) vẫn còn nằm trong deque. Cách an toàn: điều kiện cập nhật if (dist[u] + w < dist[v]) ở mỗi cạnh đã ngăn lan truyền từ bản xấu; nếu bạn lưu khoảng cách kèm phần tử trong deque, hãy thêm if (d > dist[u]) continue; ngay sau khi pop để bỏ bản cũ. Thiếu bước này có thể làm độ phức tạp phình to.

• Đẩy nhầm đầu/cuối (lẫn push_front với push_back). Đảo ngược hai lệnh này khiến deque không còn sắp theo khoảng cách, kết quả sai mà vẫn chạy. Nhớ chắc: trọng số 0 → front, trọng số 1 → back.

• Dùng queue thường thay vì deque. std::queue không có push_front; nếu vẫn cố push_back cho cả cạnh 0, thuật toán suy biến thành BFS sai vì các đỉnh "miễn phí" bị xử lý quá muộn, cho khoảng cách lớn hơn thực tế.

• Tràn số / chọn sai INF. Khởi tạo $dist=$ INT_MAX rồi tính dist[u] + w có thể tràn nếu dist[u] đã là INT_MAX. Hãy chỉ cộng khi đỉnh $u$ đã có khoảng cách hữu hạn (đỉnh lấy ra từ deque luôn hữu hạn nên thường an toàn), hoặc dùng INF nhỏ hơn như 1e9 để chừa biên.

• Áp dụng khi trọng số không thuộc $\{0,1\}$. 0-1 BFS chỉ đúng khi mọi cạnh là 0 hoặc 1. Nếu có cạnh trọng số 2 (hay bất kỳ giá trị nào khác), deque mất bất biến hai-mức và cho kết quả sai — khi đó phải dùng Dijkstra, hoặc nếu trọng số là $\{0,1,\dots ,k\}$ nhỏ thì dùng dial's algorithm / 0-k BFS.

• Quên: chi phí thuộc về cạnh, không phải đỉnh — hay nhầm khi nào tính. Trên lưới phá tường, hãy thống nhất "chi phí là khi bước vào ô đích". Nếu khởi tạo dist[src] = grid[src] rồi lại cộng grid[src] lần nữa, hoặc tính chi phí của ô nguồn hai lần, kết quả lệch. Trong code mẫu ở trên dist[0][0] = 0 và chi phí ô nguồn được coi là 0 (đã đứng sẵn ở đó).

Biến thể / Mở rộng

• 0-k BFS (dial's algorithm): khi trọng số $\in \{0,1,\dots ,k\}$ với $k$ nhỏ, dùng $k+1$ "xô" (bucket) tròn theo $distmod(k+1)$ để vẫn đạt gần $O(V+E)$.
• Nhân đôi/nhân ba trạng thái: nhiều bài lưới cần thêm chiều trạng thái vào đỉnh (vd hướng đang đi, đã có "vật phẩm" hay chưa). Đỉnh trở thành $(\text{ô},\text{trạng thái})$ và bạn chạy 0-1 BFS trên không gian trạng thái mở rộng — đây là cách giải bài laser/gương ở phần luyện tập.
• Liên hệ Dijkstra: nếu nắm 0-1 BFS, bạn đã hiểu một ca đặc biệt của Dijkstra; xem thêm trang Dijkstra để xử lý trọng số tổng quát.

Bài tập luyện

• Cõng Bạn (piggyback) — (Nghiệp dư) Bài khởi động: đồ thị không trọng số nên đường ngắn nhất tính bằng BFS thuần (mọi cạnh = 1). Làm bài này để nắm vững ý "BFS lấy đỉnh theo khoảng cách tăng dần" — đúng tiền đề mà 0-1 BFS mở rộng. (Chưa cần deque.)
• Đảo Chiều Trọng Lực (gravity) — (Trung cấp) Bài 0-1 BFS kinh điển trên lưới: đi trái/phải có chi phí 0, mỗi lần đảo chiều trọng lực tốn 1; cần push_front/push_back để tối thiểu số lần đảo.
• Laser và gương (lasers16) — (Kỳ cựu) 0-1 BFS nâng cao trên không gian trạng thái $(\text{vị trí},\text{hướng})$: đi thẳng tốn 0, đặt một gương (đổi hướng) tốn 1; minh hoạ kỹ thuật mở rộng trạng thái kèm 0-1 BFS để đếm số lần "đổi hướng" tối thiểu.