Hướng dẫn giải của [2627 KS3_DE2] Câu 4: Thoát lũ
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Trước hết loang nước từ các ô * (BFS nhiều nguồn, không qua # và D) để biết thời điểm ~w[c]~ mỗi ô bị ngập. Sau đó Nam chờ ~x~ phút ở ô S rồi chạy: đến ô ~c~ sau ~d~ bước thì cần ~x + d < w[c]~ (ô D luôn an toàn). Cần tìm ~x~ lớn nhất.
Sub 1: Thử từng x — dùng khi ~n \cdot m \le 2000~
Với mỗi ~x = 0, 1, \dots, w[S]-1~, chạy một BFS từ S kiểm tra có tới được D không (đến sớm nhất luôn là tốt nhất nên BFS là đủ), lấy ~x~ lớn nhất thỏa. Nếu S không bao giờ bị ngập (~w[S]~ vô hạn) thì chỉ cần kiểm tra ~x = 0~: tới được D thì in VOCUC, không thì -1. Nếu không có ~x~ nào thỏa in -1. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Chặt nhị phân — ~O(n \cdot m \log (n \cdot m))~
Nếu chờ ~x~ phút mà thoát được thì chờ ít hơn cũng thoát được, nên chặt nhị phân ~x~ trong ~[0, w[S]-1]~ với hàm kiểm tra là một BFS. Nếu chờ 0 phút mà không thoát thì in -1. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc từng bản đồ từ file CAU4.INP; bản đồ nhỏ (~n \cdot m \le 2000~) gọi sub1, bản đồ lớn gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, sc, dc; // kích thước, chỉ số ô S và ô D (ô (i,j) -> i*m+j)
vector<string> g;
vector<int> w; // w[c] = phút ô c bị ngập (INF nếu không bao giờ)
vector<int> dist_, q;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
// Loang nước từ các ô '*' (thời điểm 0) để tính w
void flood() {
w.assign(n * m, INF);
q.clear();
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
if (g[i][j] == '*') { w[i * m + j] = 0; q.push_back(i * m + j); }
for (size_t h = 0; h < q.size(); h++) {
int c = q[h], x = c / m, y = c % m;
for (int d = 0; d < 4; d++) {
int a = x + dx[d], b = y + dy[d];
if (a < 0 || b < 0 || a >= n || b >= m) continue;
char ch = g[a][b];
if (ch == '#' || ch == 'D') continue;
if (w[a * m + b] != INF) continue;
w[a * m + b] = w[c] + 1;
q.push_back(a * m + b);
}
}
}
// Nam đứng chờ x phút rồi chạy: có tới được D không? (BFS, ô c chỉ vào được nếu x + dist < w[c])
bool feasible(long long x) {
if (x >= w[sc]) return false;
dist_.assign(n * m, -1);
vector<int> qq = {sc};
dist_[sc] = 0;
for (size_t h = 0; h < qq.size(); h++) {
int c = qq[h], cx = c / m, cy = c % m;
for (int d = 0; d < 4; d++) {
int a = cx + dx[d], b = cy + dy[d];
if (a < 0 || b < 0 || a >= n || b >= m) continue;
int e = a * m + b;
if (g[a][b] == '#' || dist_[e] != -1) continue;
if (g[a][b] == 'D') return true;
if (x + dist_[c] + 1 >= w[e]) continue;
dist_[e] = dist_[c] + 1;
qq.push_back(e);
}
}
return false;
}
// Sub 1: thử lần lượt x = 0, 1, 2, ... (x < w[S]); mỗi lần một BFS. Dùng khi n*m nhỏ.
void sub1() {
flood();
if (w[sc] == INF) { puts(feasible(0) ? "VOCUC" : "-1"); return; }
int best = -1;
for (int x = 0; x < w[sc]; x++) if (feasible(x)) best = x;
printf("%d\n", best);
}
// Sub 2: tính chất đơn điệu (chờ càng ít càng dễ thoát) -> chặt nhị phân x, O(nm log(nm))
void sub2() {
flood();
if (w[sc] == INF) { puts(feasible(0) ? "VOCUC" : "-1"); return; }
if (!feasible(0)) { puts("-1"); return; }
int lo = 0, hi = w[sc] - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (feasible(mid)) lo = mid; else hi = mid - 1;
}
printf("%d\n", lo);
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
g.assign(n, "");
char buf[1105];
for (int i = 0; i < n; i++) {
scanf("%s", buf);
g[i] = buf;
for (int j = 0; j < m; j++) {
if (g[i][j] == 'S') sc = i * m + j;
if (g[i][j] == 'D') dc = i * m + j;
}
}
if (n * m <= 2000) sub1();
else sub2();
}
return 0;
}
Bình luận