Tác giả:
Reviewer:
Lỡ một ngày bạn ngồi trong phòng thi quốc gia, bạn gặp một đề bài như sau:
Cho một đồ thị đỉnh cạnh (), cạnh thứ có trọng số là (). Tìm đường đi ngắn nhất từ đến ().
Bạn hì hục cài Dijkstra, tuy nhiên code lại chạy quá chậm để qua được giới hạn thời gian. Lúc ấy bạn mới nhớ lại blog về 0-1 BFS trên VNOI wiki, thứ mà bạn sắp đọc bây giờ.
0-1 BFS có thể thực hiện tìm kiếm đường đi ngắn nhất từ một nguồn (Single source shortest path) trong độ phức tạp tuyến tính, với điều kiện là cạnh có trọng số bằng 0 hoặc .
0-1 BFS có rất nhiều điểm tương đồng với BFS và Dijkstra. Thay vì sử dụng hàng đợi (queue) để chứa các đỉnh sẽ được duyệt, ta sử dụng hàng đợi hai đầu (double-ended queue, thường gọi tắt là deque) để chứa các đỉnh sẽ được duyệt.
Bước 1: Khởi tạo
Bước 2: Thực hiện đến khi deque rỗng
Tính đúng đắn của 0-1 BFS có thể chứng minh như thuật toán Dijkstra. Tuy nhiên Dijkstra sử dụng cấu trúc dữ liệu hàng đợi ưu tiên để tìm đỉnh có nhỏ nhất trong các đỉnh với độ phức tạp mỗi thao tác, còn 0-1 BFS tìm đỉnh này trong .
Trong hàng đợi hai đầu, gọi là đỉnh nằm ở đầu hàng đợi, các đỉnh trong hàng đợi có tăng dần từ đầu đến cuối hàng đợi và chỉ có thể bằng hoặc :
Ta sẽ chứng minh điều này bằng phương pháp quy nạp:
Từ đây ta cũng chứng minh được một đỉnh chỉ được cập nhật và đẩy vào hàng đợi tối đa 2 lần nên độ phức tạp sẽ tương đương thuật toán BFS là
Cấu trúc dữ liệu:
MAXN: Độ lớn của mảngD[]: Tương tự trênvis[]: Mảng đánh dấu đỉnh đã được duyệtg[]: Danh sách kề của các đỉnhdq: Chứa các đỉnh sẽ được duyệtconst int INF = 1e9;
const int MAXN = 2e6+5;
int n; // Số đỉnh của đồ thị
int D[MAXN], vis[MAXN];
vector<pair<int, int>> g[MAXN]; // first là đầu mút của cạnh, second là trọng số của cạnh
deque<int> dq;
void BFS_01(int s){
for(int i = 1; i <= n; i++){
D[i] = INF; // Khởi tạo
vis[i] = 0;
}
D[s] = 0;
dq.push_front(s);
while(!dq.empty()){
int u = dq.front();
dq.pop_front();
if(vis[u])continue;
vis[u] = 1; // Đánh dấu
for(auto v: g[u]){
if(D[v.first] > D[u] + v.second){ //
D[v.first] = D[u] + v.second; // Duyệt và sử lý các cạnh của u
if(v.second == 1)dq.push_back(v.first); //
else dq.push_front(v.first);
}
}
}
}
Có rất ít bài toán yêu cầu bắt buộc phải sử dụng 0-1 BFS. Rất khó để ép thời gian sao cho Dijkstra chạy quá thời gian mà 0-1 BFS lại AC. Vì vậy 0-1 BFS thường được sử dụng trong các bài khó nhưng đưa được về đồ thị có rất nhiều đỉnh hoặc cạnh.
Ta có thể giải được bài toán tìm đường đi ngắn nhất từ một nguồn trong với là trọng số cạnh lớn nhất trong đồ thị. Ta có thể lưu hàng đợi, hàng đợi thứ ban đầu lưu các đỉnh có . Khi đã lấy hết đỉnh trong hàng đợi , ta có thể dùng lại hàng đợi đó để lưu các đỉnh có , rồi , ... Do các cạnh có trọng số không quá , một đỉnh sẽ không bao giờ cập nhật vào một hàng đợi cách hàng đợi chứa đỉnh đó quá , nên chỉ có tối đa hàng đợi không rỗng tại mỗi thời điểm.
Link nộp: Codeforces - Labyrinth
Đề bài
Bạn đang chơi một trò chơi điện tử. Một level nào đó đặt bạn vào một ô nào đó trong một mê cung hàng cột. Ta định nghĩa ô nằm trên hàng thứ a, cột thứ b là ô . Một ô có thể có chướng ngại vật hoặc không. Bạn chỉ được di chuyển trái, trên, phải, dưới, không được đi vào các ô có chướng ngại vật và không được ra ngoài mê cung.
Do bàn phím bạn sắp hỏng nên bạn chỉ được di chuyển sang trái không quá lần và sang phải không quá lần.
Biết rằng bạn đang bắt đầu ở ô , hãy đếm và in ra số ô trong mê cung đến được từ ô bắt đầu.
Giới hạn:
Lời giải
Đây là một bài cơ bản để tập cài 0-1 BFS.
Giả sử ta muốn kiểm tra xem có đến được một ô nào đó thì cần tối thiểu bao nhiêu lần đi trái/phải.
Gọi số lần đi sang trái là , số lần đi sang phải là . Dễ thấy Vì hiệu không đổi nên nếu ta tối thiểu hóa được thì cũng sẽ là tối thiểu.
Ta coi mê cung là một đồ thị, các ô vuông chung cạnh sẽ được nối với nhau trên đồ thị, cạnh nối có trọng số là nếu lên/xuống/phải và là nếu là trái. Sau khi chạy thuật toán, với mỗi ô ta sẽ biết được số bước sang trái tối thiểu, từ đó tính được số bước phải tối thiểu và kiểm tra với điều kiện đề bài.
Độ phức tạp thời gian:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3+5;
const int INF = 1e9+5;
int n, m, r, c, x, y;
char board[MAXN][MAXN];
int d[MAXN][MAXN];
int vis[MAXN][MAXN];
const pair<int, int> mv[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool in_bound(int a, int b){
return 1 <= a && a <= n && 1 <= b && b <= m && board[a][b] == '.';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> r >> c >> x >> y;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> board[i][j];
d[i][j] = INF;
}
}
d[r][c] = 0;
deque<pair<int, int>> dq;
dq.push_back({r, c});
while(!dq.empty()){
pair<int, int> u = dq.front();
dq.pop_front();
if(vis[u.first][u.second])continue;
vis[u.first][u.second] = 1;
for(pair<int, int> v: mv){
int nwx = v.first + u.first, nwy = v.second + u.second;
int w;
if(v == make_pair(0, -1))w = 1;
else w = 0;
if(in_bound(nwx, nwy) && d[nwx][nwy] > d[u.first][u.second] + w){
d[nwx][nwy] = d[u.first][u.second] + w;
if(w == 0)dq.push_front({nwx, nwy});
else dq.push_back({nwx, nwy});
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int l = d[i][j], r = l + j - c;
if(l <= x && r <= y)ans++;
}
}
cout << ans;
}
Link nộp: Codeforces - Chamber of Secrets
Đề bài
Cho căn phòng có thể chia thành bảng lưới gồm hàng và cột. Mỗi ô trong bảng lưới có thể chứa một chiếc gương ma thuật hoặc không chứa gì. Nếu kích hoạt gương ma thuật, ánh sáng chiếu vào gương sẽ bị phản chiếu ra 4 phía trái, trên, phải, xuống (xem hình trong đề bài gốc để dễ hiểu hơn).
Có một tia sáng chiếu từ cạnh bên trái của ô chiếu từ trái sang phải và một cánh cửa nằm trên cạnh bên phải của ô . Tìm số gương cần kích hoạt tối thiểu để tia sáng đến được cánh cửa.
Giới hạn:
Lời giải
Để có tia sáng tới được cánh cửa, tương đương với việc phải tồn tại một đường đi bắt đầu bằng một chiếc gương ở hàng , kết thúc bằng một chiếc gương ở hàng , và hai gương liên tiếp cùng hàng hoặc cùng cột. Nói cách khác, cần tìm một dãy gương sao cho:
Ta có nhận xét: Nếu tồn tại sao cho hoặc thì ta có thể bỏ chiếc gương thứ này đi. Do đó, số gương tối ưu tương đương với số lần tia sáng phải đổi phương từ ngang thành dọc và ngược lại.
Đến đây, ta có lời giải như sau:
Đáp án của bài toán là đường đi ngắn nhất từ ô trong đồ thị đến ô trong đồ thị . Ta tìm đường đi ngắn nhất bằng 0-1 BFS.
Độ phức tạp thời gian:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
const int INF = 1e9+5;
vector<pair<int, int>> g[MAXN*MAXN*2];
int d[MAXN*MAXN*2], vis[MAXN*MAXN*2];
int encode(int type, int i, int j) { // mã hóa ô (i, j) của đồ thị type thành 1 số
return (type-1)*MAXN*MAXN + i*MAXN + j;
}
void add_edge(int a, int b, int w) {
g[a].push_back({b, w});
g[b].push_back({a, w});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char x;
cin >> x;
d[encode(1, i, j)] = INF;
d[encode(2, i, j)] = INF;
if(x == '#')add_edge(encode(1, i, j), encode(2, i, j), 1);
if(j > 1)add_edge(encode(1, i, j-1), encode(1, i, j), 0);
if(i > 1)add_edge(encode(2, i-1, j), encode(2, i, j), 0);
}
}
deque<int> dq;
d[encode(1, 1, 1)] = 0;
dq.push_front(encode(1, 1, 1));
while(!dq.empty()){
auto u = dq.front();
if(u == encode(1, n, m)){
cout << d[u];
return 0;
}
dq.pop_front();
if(vis[u])continue;;
vis[u] = 1;
for(pair<int, int> v: g[u]){
if(d[v.first] > d[u] + v.second){
d[v.first] = d[u] + v.second;
if(!v.second)dq.push_front(v.first);
else dq.push_back(v.first);
}
}
}
cout << "-1";
}