# BFS 0-1

## Thuật toán
Thuật toán BFS 0-1 là một dạng mở rộng của [thuật toán tìm kiếm theo chiều sâu (BFS)](https://vnoi.info/wiki/algo/graph-theory/breadth-first-search.md), và cũng là một trường hợp đặc biệt của [thuật toán Dijkstra](https://vnoi.info/wiki/algo/graph-theory/shortest-path.md#2-thu%E1%BA%ADt-to%C3%A1n-dijkstra). So với thuật toán BFS, điểm khác biệt chính của thuật toán BFS 0-1 là việc sử dụng hàng đợi hai đầu để lưu thứ tự duyệt qua các đỉnh.

1. Khởi tạo hàng đợi $Q$ và đẩy đỉnh phát (source) $s$ vào $Q$.
2. Lấy phần tử đầu tiên (gọi là đỉnh $u$) ra khỏi hàng đợi $Q$. Nếu đỉnh $u$ đã được xử lý thì bỏ qua, nếu không thì chuyển sang bước 3.
3. Xét tất cả các cạnh nối $u$ với đỉnh $v$ có trọng số $w$. Nếu $\text{dist}[u] + w < \text{dist}[v]$ thì cập nhật lại $\text{dist}[v]$ theo $\text{dist}[u]$ và chèn vào hàng đợi:
- Nếu $w = 0$, chèn đỉnh $v$ vào đầu hàng đợi.
- Nếu $w = 1$, chèn đỉnh $v$ vào cuối hàng đợi.
4. Đỉnh $u$ đã được xử lý. Nếu hàng đợi vẫn còn phần tử thì quay lại bước 2.
5. Thuật toán duyệt hoàn tất.

Bạn đọc có thể theo dõi hình dưới để hiểu rõ thuật toán BFS 0-1:

## Giải thích nguyên lý
Trong thuật toán Dijkstra, khi duyệt qua các đỉnh trong hàng đợi, khoảng cách của mỗi đỉnh đến đỉnh phát sẽ có giá trị tăng dần. Nói cách khác:

$$
Q = \{q_1, q_2, q_3, \dots, q_m\} \\
\text{dist}[q_1] \le \text{dist}[q_2] \le \text{dist}[q_3] \le \dots \le \text{dist}[q_m]
$$

Hàng đợi ở trên đang trong trạng thái chuẩn bị duyệt qua đỉnh $q_1$. Khi xét qua các cạnh $(q_1, v)$ với trọng số $w$:
- Nếu $w = 0$: khi này, $\text{dist}[v] = \text{dist}[q_1] \le \text{dist}[q_i]$ với mọi $i = 2\dots m$. Do ta chỉ quan tâm đến giá trị khoảng cách tăng cần nên đỉnh $v$ sẽ luôn được chèn vào đầu hàng đợi.
- Nếu $w = 1$:
- Xét đỉnh $q_m$ nằm ở cuối hàng đợi. Gọi $q'$ là đỉnh tác động làm thay đổi $\text{dist}[q_m]$. Khi này: $\text{dist}[q_m] - \text{dist}[q'] = w' \le 1$.
- Vì đỉnh $q'$ được xử lý trước đỉnh $q_1$ nên $\text{dist}[q'] \le \text{dist}[q_1]$. Suy ra: $\text{dist}[q_m] - \text{dist}[q_1] \le \text{dist}[q_m] - \text{dist}[q'] \le 1$. Từ đó rút ra: $\text{dist}[q_m] \le \text{dist}[q_1] + 1$. Do đó, $\text{dist}[q_1] + 1$ sẽ luôn là giá trị lớn nhất trong lúc xét và ta có thể chèn đỉnh $v$ vào cuối hàng đợi.

Từ các nhận xét trên, ta nhận thấy đỉnh mới chỉ được chèn tại đầu hoặc cuối hàng đợi. Thay vì sử dụng hàng đợi ưu tiên (`priority_queue` hoặc `set` trong C++), ta có thể sử dụng hàng đợi hai đầu (`deque` trong C++) để giảm độ phức tạp thời gian của các thao tác với hàng đợi xuống $O(1)$, nhanh hơn so với thuật toán Dijkstra.

## Đánh giá thuật toán
Gọi $|E|$ là số cạnh của đồ thị và $|V|$ là số đỉnh của đồ thị.
Độ phức tạp thời gian của thuật toán là $O(|E| + |V|)$.
Độ phức tạp không gian của thuật toán là $O(|E|)$.

## Cài đặt

struct Edge { int v, w; }; // cạnh đồ thị

bool visited[MAXN]; // kiểm tra đỉnh này đã được xử lý chưa
int dist[MAXN]; // khoảng cách đến đỉnh phát của mỗi đỉnh
vector<Edge> g[MAXN]; // danh sách kề biểu diễn đồ thị

void bfs(int s) {
    deque<int> q;
    q.push_back(s);
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        if (visited[u]) continue;
        visited[u] = true;
        for (Edge e : g[u]) {
            int v = e.v, w = e.w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0)
                    q.push_front(v);
                else
                    q.push_back(v);
            }
        }
    }
}

## Bài toán ví dụ
Nguồn: [UVA - Ocean Currents](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2620)
### Tóm tắt
Cho ma trận $A$ kích thước $R \times C$, từ một ô bất kỳ ta có thể di chuyển sang một ô khác trên ma trận theo một trong tám hướng (đông, tây, nam, bắc, đông bắc, tây bắc, đông nam, tây nam) với chi phí là $1$. Ngoài ra, mỗi ô ghi một hướng mà nếu di chuyển theo hướng này thì chi phí là $0$.

Cho $N$ truy vấn. Với mỗi truy cấn, tìm đường đi từ ô $(r_s, c_s)$ đến ô $(r_d, c_d)$ với chi phí nhỏ nhất.

Giới hạn: $R, C \le 1000, N \le 50$
### Cách giải
Xét ma trận $A$ như một đồ thị vô hướng: mỗi ô trên ma trận tương ứng với một đỉnh của đồ thị, hai ô có thể đến được nhau được nối bởi một cạnh của đồ thị. Với mỗi ô $A_{i,j}$, ta xét hướng đi ghi trên ô này sẽ dẫn đến vị trí nào (gọi là $A_{i',j'}$). Nếu vị trí mới vẫn nằm trong phạm vi của ma trận, ta sẽ gán trọng số $0$ lên cạnh nối $(A_{i,j}, A_{i',j'})$. Tất cả những cạnh còn lại chưa được gán trọng số là những trường hợp còn lại và sẽ được gán trọng số $1$.

Từ việc đồ thị hóa bài toán, dễ thấy ta chỉ cần sử dụng thuật toán tìm đường đi ngắn nhất để trả lời cho mỗi truy vấn. Một hướng suy nghĩ là sử dụng thuật toán Dijkstra; tuy nhiên, do độ phức tạp thời gian khi trả lời mỗi truy vấn là $O(R\cdot C\cdot\log(RC))$ nên độ phức tạp thời gian cuối cùng sẽ là $O(N\cdot R\cdot C\cdot\log(RC))$. Ước chừng theo giới hạn, $N \cdot R \cdot C \cdot \log(RC) \approx 10^9$ phép toán, nếu giới hạn thời gian của bài toán chặt thì khả năng cao cách trả lời bằng thuật toán Dijkstra sẽ vượt quá thời gian cho phép.

Từ tính chất mỗi cạnh chỉ mang một trong hai trọng số $0$ hoặc $1$, ta sẽ áp dụng thuật toán BFS 0-1 để trả lời truy vấn. Mỗi truy vấn sẽ tìm câu trả lời với độ phức tạp thời gian là $O(R\cdot C)$, tổng độ phức tạp thời gian của thuật toán là $O(N \cdot R \cdot C)$. Với giới hạn đã cho, do $N \cdot R \cdot C \le 50M$ phép toán nên thuật toán có thể chạy trong giới hạn 1 giây.

### Cài đặt mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1003;
const int INF = 1e9 + 7;

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

struct Cell { int x, y; };

int rows, cols, n;
bool marked[MAXN][MAXN];
int dist[MAXN][MAXN];
string a[MAXN];

void reset() {
    for (int i = 0; i < rows; ++i) {
        fill(dist[i], dist[i] + cols, INF);
        fill(marked[i], marked[i] + cols, false);
    }
}

int bfs(int rs, int cs, int rd, int cd) {
    deque<Cell> q;
    q.push_back(Cell{rs, cs});
    dist[rs][cs] = 0;
    while (!q.empty()) {
        Cell u = q.front();
        q.pop_front();
        int xu = u.x, yu = u.y;
        if (marked[xu][yu]) continue;
        marked[xu][yu] = 1;
        if (xu == rd && yu == cd)
            return dist[xu][yu];
        for (int t = 0; t < 8; ++t) {
            int xv = xu + dx[t], yv = yu + dy[t];
            if (xv < 0 || xv >= rows || yv < 0 || yv >= cols)
                continue;
            int w = (t == (a[xu][yu] - '0') ? 0 : 1);
            if (dist[xu][yu] + w < dist[xv][yv]) {
                dist[xv][yv] = dist[xu][yu] + w;
                if (w == 0)
                    q.push_front(Cell{xv, yv});
                else
                    q.push_back(Cell{xv, yv});
            }
        }
    }
    return -1;
}

int main() {
    cin >> rows >> cols;
    for (int i = 0; i < rows; ++i)
        cin >> a[i];
    cin >> n;
    while (n--) {
        int rs, cs, rd, cd;
        cin >> rs >> cs >> rd >> cd;
        --rs, --cs, --rd, --cd;
        reset();
        cout << bfs(rs, cs, rd, cd) << "\n";
    }
}

## Bài tập áp dụng
[Leetcode - Minimum Cost to Make At Least One Valid Path in a Grid](https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid)
[Codechef - Chef and Reverse](https://www.codechef.com/problems/REVERSE)
[SPOJ - KATHTHI](http://www.spoj.com/problems/KATHTHI/)
[Codeforces - Labyrinth](https://codeforces.com/contest/1063/problem/B)
[Codeforces - Three States](https://codeforces.com/problemset/problem/590/C)
[Codeforces - Olya and Energy Drinks](https://codeforces.com/problemset/problem/877/D)
[UVA - Colliding Traffic](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2621)
[BOI 2013 - Tracks in the Snow](https://oj.uz/problem/view/BOI13_tracks)