Ngăn mặn (Đề tự luyện HSG Tin quốc gia – Bài 2)
Đề bài
Ngăn mặn
Khu đất là lưới $N \times M$. Ô ghi chữ số $1..9$ là đất trũng, đắp đê ở đó tốn đúng chừng ấy công; ô 0 là gò cao (coi như có đê sẵn, không tốn công); ô X là ao, mương: không đắp được, nước qua tự do.
Nước mặn tràn vào mọi ô không có đê ở cột $1$, rồi lan sang các ô chung cạnh không có đê (không lan qua chỗ hai ô chỉ chung một góc). Hãy đắp đê sao cho nước mặn không tới được ô nào ở cột $M$, với tổng số công ít nhất; in $-1$ nếu không thể.
Dữ liệu vào: dòng đầu $N, M$ $(1 \le N, M \le 1000)$; $N$ dòng sau, mỗi dòng một xâu độ dài $M$ gồm các ký tự 0–9 và X.
Kết quả: tổng số công ít nhất, hoặc $-1$.
- Subtask 1 (15%): $N \times M \le 16$.
- Subtask 2 (20%): $N, M \le 40$.
- Subtask 3 (25%): lưới chỉ gồm
0,1vàX. - Subtask 4 (40%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.
5 7
5001098
70XX006
6297214
6000775
X8438515Đắp đê ở ô $(3, 2)$ (2 công) và ô $(5, 4)$ (3 công). Nước mặn chỉ tràn tới bảy ô $(1,1), (2,1), (3,1), (4,1), (5,1), (5,2), (5,3)$ rồi dừng. Không có cách nào tốn ít hơn 5 công.
3 4
1X95
4XXX
XX27-1Dải mương $(3,1), (3,2), (2,2), (2,3), (2,4)$ nối liền theo cạnh từ cột 1 sang cột 4 và không đắp được, nên nước mặn luôn tới cột 4.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Ngăn mặnLời mở đầu
Đọc kỹ đề ta thấy đây là một bài lát cắt: phải "cắt" (đắp đê) một số ô để không còn đường đi theo cạnh nào từ cột $1$ sang cột $M$ qua các ô không có đê, và muốn tổng chi phí các ô bị cắt nhỏ nhất. Ai đã học luồng sẽ nghĩ ngay tới lát cắt cực tiểu = luồng cực đại (Cách 2). Nhưng với lưới $1000 \times 1000$ thì luồng quá chậm. Mấu chốt của bài nằm ở việc nhìn bức tường đê từ một phía khác.
Thử tưởng tượng một bức tường đê chặn được nước: nó phải "kéo" từ mép Bắc xuống mép Nam, nếu không nước sẽ vòng qua chỗ hở. Câu hỏi là các ô đê trong bức tường phải nối với nhau thế nào? Vì nước không đi chéo, hai ô đê chỉ chung nhau một góc đã đủ kín:
Bên trái: 4 ô đê nối nhau theo đường chéo từ hàng 1 xuống hàng 4 – nước không có cách nào chen qua. Bên phải: bỏ một ô đê là có lỗ hổng.
0 cũng là ô đê. Nước mặn không tới được cột $M$ khi và chỉ khi có một dãy ô đê đi từ một ô ở hàng $1$ xuống một ô ở hàng $N$, trong đó hai ô liên tiếp chung cạnh hoặc chung góc (8 hướng).Vì vậy đáp án = đường đi ngắn nhất từ hàng $1$ xuống hàng $N$, đi theo 8 hướng, không đi vào ô
X, độ dài đường đi là tổng các chữ số trên các ô đi qua (kể cả ô đầu). Không có đường nào thì in $-1$.Vì sao đúng? Nếu có bức tường 8 hướng như vậy, mọi đường nước đi theo cạnh từ Tây sang Đông đều phải cắt qua nó; đường nước không thể "lách" giữa hai ô đê chéo nhau vì muốn lách thì phải đi chéo. Ngược lại, nếu các ô đê không nối được từ hàng $1$ xuống hàng $N$ theo 8 hướng, thì phần đất bị các nhóm ô đê "chạm mép Bắc" bao lại không chạm mép Nam, nước luôn tìm được lối vòng phía dưới chúng (đây là cùng một sự thật với trò chơi Hex: trên bàn cờ đã tô kín, đúng một trong hai người nối được hai cạnh của mình). Khi đó lát cắt cực tiểu trên đồ thị "nước đi 4 hướng" trở thành đường đi ngắn nhất trên đồ thị "đê đi 8 hướng" – một ví dụ đẹp của đồ thị đối ngẫu.
Lộ trình:
Trước khi vào các cách, các em có thể tự "đắp đê" và xem nước lan thế nào ở mô phỏng dưới đây (thử bỏ một ô đê, hoặc đặt các ô đê chéo nhau):
Cách 1Thử mọi tập ô đê – O(2^K · NM) · 15%
Gọi $K$ là số ô đất trũng (chữ số $1..9$). Với $N \times M \le 16$ thì $K \le 16$: thử cả $2^K$ cách chọn tập ô đắp đê (ô 0 luôn là đê, ô X không bao giờ là đê). Với mỗi cách, cho nước lan bằng BFS từ các ô không có đê ở cột $1$ (chỉ đi 4 hướng, không vào ô có đê); nếu không chạm cột $M$ thì cập nhật đáp án bằng tổng công. Code C++ duyệt các tập bằng một "số nhị phân" pick cộng dần từng đơn vị, bản Python dùng mặt nạ bit.
#include <bits/stdc++.h>
using namespace std;
// Cach 1: thu moi tap o dap de (dem nhi phan), BFS kiem tra nuoc man co toi cot M khong
int n, m;
vector<string> g;
bool safe(const vector<char> &blk) { // true neu nuoc man khong toi cot M
vector<char> vis(n * m, 0);
queue<int> q;
for (int i = 0; i < n; i++)
if (!blk[i * m]) { vis[i * m] = 1; q.push(i * m); }
while (!q.empty()) {
int u = q.front(); q.pop();
int i = u / m, j = u % m;
if (j == m - 1) return false;
int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int a = i + di[k], b = j + dj[k];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
int v = a * m + b;
if (!blk[v] && !vis[v]) { vis[v] = 1; q.push(v); }
}
}
return true;
}
int main() {
cin >> n >> m;
g.resize(n);
for (auto &s : g) cin >> s;
vector<int> cells; // cac o dat trung (chi phi 1..9)
vector<char> blk(n * m, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (g[i][j] == '0') blk[i * m + j] = 1; // go cao: luon chan nuoc
else if (g[i][j] != 'X') cells.push_back(i * m + j);
}
int K = cells.size();
vector<char> pick(K, 0);
long long best = -1;
while (true) {
long long cost = 0;
for (int t = 0; t < K; t++) {
blk[cells[t]] = pick[t];
if (pick[t]) cost += g[cells[t] / m][cells[t] % m] - '0';
}
if ((best < 0 || cost < best) && safe(blk)) best = cost;
int t = 0; // sang tap tiep theo (cong 1 vao so nhi phan pick)
while (t < K && pick[t]) pick[t++] = 0;
if (t == K) break;
pick[t] = 1;
}
cout << best << "\n";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.read().split()
n = int(data[0]); m = int(data[1]); g = data[2:2 + n]
cells = [] # cac o dat trung (chi phi 1..9)
blk = [0] * (n * m)
for i in range(n):
for j in range(m):
if g[i][j] == '0':
blk[i * m + j] = 1 # go cao: luon chan nuoc
elif g[i][j] != 'X':
cells.append(i * m + j)
K = len(cells)
best = -1
for mask in range(1 << K):
cost = 0
for t in range(K):
if mask >> t & 1:
blk[cells[t]] = 1; cost += int(g[cells[t] // m][cells[t] % m])
else:
blk[cells[t]] = 0
if best >= 0 and cost >= best:
continue
vis = [0] * (n * m); q = deque(); bad = False
for i in range(n):
if not blk[i * m]:
vis[i * m] = 1; q.append(i * m)
while q:
u = q.popleft(); i = u // m; j = u % m
if j == m - 1:
bad = True
break
for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= a < n and 0 <= b < m:
v = a * m + b
if not blk[v] and not vis[v]:
vis[v] = 1; q.append(v)
if not bad:
best = cost
print(best)
main()Cách 2Luồng cực đại – lát cắt đỉnh nhỏ nhất · 35%
Đây đúng là bài toán lát cắt đỉnh: xóa (đắp đê) một tập đỉnh có tổng trọng số nhỏ nhất để không còn đường từ "nguồn" (sông) tới "đích" (ruộng). Kỹ thuật chuẩn là tách đỉnh: mỗi ô $v$ thành hai đỉnh $v_{vào} \to v_{ra}$ với sức chứa bằng số công đắp ô đó (ô 0: sức chứa $0$; ô X: vô cùng). Các cạnh khác đều có sức chứa vô cùng:
- nguồn $S \to v_{vào}$ cho mọi ô ở cột $1$; $v_{ra} \to$ đích $T$ cho mọi ô ở cột $M$;
- $u_{ra} \to v_{vào}$ cho mọi cặp ô $u, v$ chung cạnh (nước đi 4 hướng).
Theo định lý luồng cực đại – lát cắt cực tiểu, giá trị luồng cực đại từ $S$ tới $T$ bằng tổng công nhỏ nhất. Luồng đạt "vô cùng" nghĩa là không cắt được ⇒ $-1$. Code dùng thuật toán Dinic; với lưới $40 \times 40$ (3 200 đỉnh) chạy rất nhanh, nhưng với $10^6$ ô thì đồ thị có $2\cdot 10^6$ đỉnh và luồng có thể lên tới vài nghìn – quá chậm (đo thực tế trên 20 giây).
#include <bits/stdc++.h>
using namespace std;
// Cach 2: lat cat dinh nho nhat = luong cuc dai (Dinic), moi o tach thanh 2 dinh vao/ra
const int INF = 1000000000;
struct E { int to, cap; };
vector<E> es;
vector<vector<int>> adj;
vector<int> lv, it;
void add(int u, int v, int c) {
adj[u].push_back(es.size()); es.push_back({v, c});
adj[v].push_back(es.size()); es.push_back({u, 0});
}
bool bfs(int s, int t) {
fill(lv.begin(), lv.end(), -1);
queue<int> q; q.push(s); lv[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int id : adj[u])
if (es[id].cap > 0 && lv[es[id].to] < 0) { lv[es[id].to] = lv[u] + 1; q.push(es[id].to); }
}
return lv[t] >= 0;
}
int dfs(int u, int t, int f) {
if (u == t) return f;
for (int &i = it[u]; i < (int)adj[u].size(); i++) {
E &e = es[adj[u][i]];
if (e.cap > 0 && lv[e.to] == lv[u] + 1) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) { e.cap -= d; es[adj[u][i] ^ 1].cap += d; return d; }
}
}
return 0;
}
int main() {
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &s : g) cin >> s;
int V = 2 * n * m + 2, S = V - 2, T = V - 1;
adj.assign(V, {}); lv.assign(V, 0); it.assign(V, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int v = i * m + j;
int c = g[i][j] == 'X' ? INF : g[i][j] - '0';
add(2 * v, 2 * v + 1, c); // dap o v ton c cong
if (j == 0) add(S, 2 * v, INF); // nuoc man vao tu cot 1
if (j == m - 1) add(2 * v + 1, T, INF); // ruong o cot M
int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int a = i + di[k], b = j + dj[k];
if (a >= 0 && a < n && b >= 0 && b < m) add(2 * v + 1, 2 * (a * m + b), INF);
}
}
long long flow = 0;
while (bfs(S, T) && flow < INF) {
fill(it.begin(), it.end(), 0);
while (int f = dfs(S, T, INF)) { flow += f; if (flow >= INF) break; }
}
cout << (flow >= INF ? -1 : flow) << "\n";
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.read().split()
n = int(data[0]); m = int(data[1]); g = data[2:2 + n]
INF = 10 ** 9
V = 2 * n * m + 2; S = V - 2; T = V - 1
to = []; cap = []; adj = [[] for _ in range(V)]
def add(u, v, c):
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
for i in range(n):
for j in range(m):
v = i * m + j
c = INF if g[i][j] == 'X' else int(g[i][j])
add(2 * v, 2 * v + 1, c) # dap o v ton c cong
if j == 0:
add(S, 2 * v, INF) # nuoc man vao tu cot 1
if j == m - 1:
add(2 * v + 1, T, INF) # ruong o cot M
for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= a < n and 0 <= b < m:
add(2 * v + 1, 2 * (a * m + b), INF)
flow = 0
while flow < INF:
lv = [-1] * V; lv[S] = 0; q = deque([S]) # BFS chia muc
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and lv[to[e]] < 0:
lv[to[e]] = lv[u] + 1; q.append(to[e])
if lv[T] < 0:
break
it = [0] * V
while True: # tim duong tang luong bang DFS lap
path = []; u = S
while u != T:
found = False
while it[u] < len(adj[u]):
e = adj[u][it[u]]
if cap[e] > 0 and lv[to[e]] == lv[u] + 1:
found = True
break
it[u] += 1
if found:
path.append(e); u = to[e]
else:
if u == S:
break
lv[u] = -1 # dinh cut, bo qua
e = path.pop(); u = to[e ^ 1]; it[u] += 1
if u != T:
break
f = min(cap[e] for e in path)
for e in path:
cap[e] -= f; cap[e ^ 1] += f
flow += f
if flow >= INF:
break
print(-1 if flow >= INF else flow)
main()Cách 3Đối ngẫu: đường đi 8 hướng, BFS 0-1 · 60%
Áp dụng nhận xét chính: đáp án là đường đi ngắn nhất từ hàng $1$ xuống hàng $N$ theo 8 hướng, "giá" của một ô là chữ số trên ô đó. Khi lưới chỉ có 0, 1, X, mọi giá là $0$ hoặc $1$ nên dùng BFS 0-1: một hàng đợi hai đầu, đi vào ô giá $0$ thì đẩy lên đầu, ô giá $1$ thì đẩy xuống cuối. Khởi tạo: mọi ô (không phải X) ở hàng $1$ có khoảng cách bằng giá của chính nó. Ô đầu tiên ở hàng $N$ được lấy ra khỏi hàng đợi cho ta đáp án.
Mẹo cài đặt: thêm một viền ô "không đi được" quanh lưới (mảng phẳng kích thước $(N+2)(M+2)$), khi đó 8 ô kề của ô $u$ là $u \pm 1$, $u \pm W$, $u \pm W \pm 1$ với $W = M + 2$, khỏi kiểm tra biên.
Lưới có chữ số $\ge 2$ (subtask 1, 2) thì code dưới vẫn gọi luồng như Cách 2 để giữ điểm.
#include <bits/stdc++.h>
using namespace std;
// Cach 3: luoi chi co 0, 1, X -> BFS 0-1 tren cac o (8 huong) tu hang 1 xuong hang N;
// cac luoi khac (subtask 1, 2) van dung luong cuc dai nhu Cach 2
const int INF = 1000000000;
struct E { int to, cap; };
vector<E> es;
vector<vector<int>> adj;
vector<int> lv, it;
void add(int u, int v, int c) {
adj[u].push_back(es.size()); es.push_back({v, c});
adj[v].push_back(es.size()); es.push_back({u, 0});
}
bool bfs(int s, int t) {
fill(lv.begin(), lv.end(), -1);
queue<int> q; q.push(s); lv[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int id : adj[u])
if (es[id].cap > 0 && lv[es[id].to] < 0) { lv[es[id].to] = lv[u] + 1; q.push(es[id].to); }
}
return lv[t] >= 0;
}
int dfs(int u, int t, int f) {
if (u == t) return f;
for (int &i = it[u]; i < (int)adj[u].size(); i++) {
E &e = es[adj[u][i]];
if (e.cap > 0 && lv[e.to] == lv[u] + 1) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) { e.cap -= d; es[adj[u][i] ^ 1].cap += d; return d; }
}
}
return 0;
}
long long flowSolve(int n, int m, const vector<string> &g) { // Cach 2
int V = 2 * n * m + 2, S = V - 2, T = V - 1;
adj.assign(V, {}); lv.assign(V, 0); it.assign(V, 0);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int v = i * m + j;
int c = g[i][j] == 'X' ? INF : g[i][j] - '0';
add(2 * v, 2 * v + 1, c); // dap o v ton c cong
if (j == 0) add(S, 2 * v, INF); // nuoc man vao tu cot 1
if (j == m - 1) add(2 * v + 1, T, INF); // ruong o cot M
int di[4] = {-1, 1, 0, 0}, dj[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int a = i + di[k], b = j + dj[k];
if (a >= 0 && a < n && b >= 0 && b < m) add(2 * v + 1, 2 * (a * m + b), INF);
}
}
long long flow = 0;
while (bfs(S, T) && flow < INF) {
fill(it.begin(), it.end(), 0);
while (int f = dfs(S, T, INF)) { flow += f; if (flow >= INF) break; }
}
return flow >= INF ? -1 : flow;
}
long long bfs01(int n, int m, const vector<string> &g) { // Cach 3
int W = m + 2, H = n + 2;
vector<int> c(H * W, -1), dist(H * W, INT_MAX); // -1: khong dap duoc (X hoac vien)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (g[i - 1][j - 1] != 'X') c[i * W + j] = g[i - 1][j - 1] - '0';
deque<int> dq;
for (int j = 1; j <= m; j++) {
int v = W + j;
if (c[v] < 0) continue;
dist[v] = c[v];
if (c[v] == 0) dq.push_front(v); else dq.push_back(v);
}
const int off[8] = {-W - 1, -W, -W + 1, -1, 1, W - 1, W, W + 1};
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
if (u / W == n) return dist[u];
for (int k = 0; k < 8; k++) {
int v = u + off[k];
if (c[v] < 0 || dist[u] + c[v] >= dist[v]) continue;
dist[v] = dist[u] + c[v];
if (c[v] == 0) dq.push_front(v); else dq.push_back(v);
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> g(n);
bool only01 = true;
for (auto &s : g) {
cin >> s;
for (char ch : s) if (ch != '0' && ch != '1' && ch != 'X') only01 = false;
}
cout << (only01 ? bfs01(n, m, g) : flowSolve(n, m, g)) << "\n";
return 0;
}import sys
from collections import deque
# Cach 3: luoi chi co 0, 1, X -> BFS 0-1 tren cac o (8 huong); cac luoi khac dung luong cuc dai nhu Cach 2
def flow_solve(n, m, g): # Cach 2
INF = 10 ** 9
V = 2 * n * m + 2; S = V - 2; T = V - 1
to = []; cap = []; adj = [[] for _ in range(V)]
def add(u, v, c):
adj[u].append(len(to)); to.append(v); cap.append(c)
adj[v].append(len(to)); to.append(u); cap.append(0)
for i in range(n):
for j in range(m):
v = i * m + j
c = INF if g[i][j] == 'X' else int(g[i][j])
add(2 * v, 2 * v + 1, c) # dap o v ton c cong
if j == 0:
add(S, 2 * v, INF) # nuoc man vao tu cot 1
if j == m - 1:
add(2 * v + 1, T, INF) # ruong o cot M
for a, b in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= a < n and 0 <= b < m:
add(2 * v + 1, 2 * (a * m + b), INF)
flow = 0
while flow < INF:
lv = [-1] * V; lv[S] = 0; q = deque([S]) # BFS chia muc
while q:
u = q.popleft()
for e in adj[u]:
if cap[e] > 0 and lv[to[e]] < 0:
lv[to[e]] = lv[u] + 1; q.append(to[e])
if lv[T] < 0:
break
it = [0] * V
while True: # tim duong tang luong bang DFS lap
path = []; u = S
while u != T:
found = False
while it[u] < len(adj[u]):
e = adj[u][it[u]]
if cap[e] > 0 and lv[to[e]] == lv[u] + 1:
found = True
break
it[u] += 1
if found:
path.append(e); u = to[e]
else:
if u == S:
break
lv[u] = -1 # dinh cut, bo qua
e = path.pop(); u = to[e ^ 1]; it[u] += 1
if u != T:
break
f = min(cap[e] for e in path)
for e in path:
cap[e] -= f; cap[e ^ 1] += f
flow += f
if flow >= INF:
break
return -1 if flow >= INF else flow
def bfs01(n, m, g): # Cach 3
W = m + 2; H = n + 2
c = [-1] * (H * W) # -1: khong dap duoc (X hoac vien)
for i in range(1, n + 1):
row = g[i - 1]; base = i * W
for j in range(m):
if row[j] != 'X':
c[base + j + 1] = ord(row[j]) - 48
INF = 1 << 60
dist = [INF] * (H * W)
dq = deque()
for j in range(1, m + 1):
v = W + j
if c[v] >= 0:
dist[v] = c[v]
if c[v] == 0:
dq.appendleft(v)
else:
dq.append(v)
offs = (-W - 1, -W, -W + 1, -1, 1, W - 1, W, W + 1)
lo = n * W; hi = lo + W
while dq:
u = dq.popleft()
if lo <= u < hi:
return dist[u]
du = dist[u]
for o in offs:
v = u + o
cv = c[v]
if cv >= 0 and du + cv < dist[v]:
dist[v] = du + cv
if cv == 0:
dq.appendleft(v)
else:
dq.append(v)
return -1
def main():
data = sys.stdin.read().split()
n = int(data[0]); m = int(data[1]); g = data[2:2 + n]
only01 = all(ch in "01X" for row in g for ch in row)
print(bfs01(n, m, g) if only01 else flow_solve(n, m, g))
main()Cách 4Đối ngẫu + Dijkstra với 10 "giỏ" – O(NM) · 100%
Với giá $0..9$ thì cần Dijkstra. Có thể dùng priority_queue ($O(NM \log NM)$, vẫn kịp), nhưng vì giá nhỏ nên có cách gọn và nhanh hơn: thuật toán Dial. Ta xét các khoảng cách $d = 0, 1, 2, \ldots$ theo thứ tự tăng dần, mỗi giá trị có một "giỏ" chứa các ô đang có khoảng cách $d$. Khi lấy ô $u$ (khoảng cách $d$) ra và đi sang ô kề $v$, khoảng cách mới là $d + c_v \le d + 9$. Vì thế tại mọi thời điểm chỉ có 10 giỏ $d, d+1, \ldots, d+9$ là còn dùng: ta dùng 10 giỏ xoay vòng, giỏ số d % 10.
- Một ô có thể bị đẩy vào giỏ nhiều lần (mỗi lần khoảng cách giảm); khi lấy ra mà
dist[u] != dthì đó là bản cũ, bỏ qua. - Ô đầu tiên ở hàng $N$ được lấy ra (với khoảng cách đúng) cho ngay đáp án; nếu hết giỏ mà chưa chạm hàng $N$ thì in $-1$.
- Đáp án tối đa $9 \cdot 10^6$, vừa kiểu
int.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int W = m + 2, H = n + 2; // them vien 1 o quanh luoi
vector<signed char> c(H * W, -1); // -1: khong dap duoc (X hoac vien)
static char row[1005];
for (int i = 1; i <= n; i++) {
if (scanf("%s", row) != 1) return 0;
for (int j = 1; j <= m; j++)
if (row[j - 1] != 'X') c[i * W + j] = row[j - 1] - '0';
}
const int INF = INT_MAX;
vector<int> dist(H * W, INF);
vector<int> bucket[10]; // Dijkstra voi trong so 0..9: 10 gio vong
for (int j = 1; j <= m; j++) {
int v = W + j;
if (c[v] >= 0) { dist[v] = c[v]; bucket[c[v]].push_back(v); }
}
const int off[8] = {-W - 1, -W, -W + 1, -1, 1, W - 1, W, W + 1}; // 8 o chung canh hoac chung dinh
int left = 0;
for (int b = 0; b < 10; b++) left += bucket[b].size();
int ans = -1;
for (int d = 0; left > 0; d++) {
vector<int> &B = bucket[d % 10];
while (!B.empty()) {
int u = B.back(); B.pop_back(); left--;
if (dist[u] != d) continue; // ban cu, da co duong tot hon
if (u / W == n) { ans = d; left = 0; break; } // cham hang cuoi
for (int k = 0; k < 8; k++) {
int v = u + off[k];
if (c[v] < 0) continue;
int nd = d + c[v];
if (nd < dist[v]) { dist[v] = nd; bucket[nd % 10].push_back(v); left++; }
}
}
}
printf("%d\n", ans);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
W = m + 2; H = n + 2 # them vien 1 o quanh luoi
c = [-1] * (H * W) # -1: khong dap duoc (X hoac vien)
for i in range(1, n + 1):
row = data[1 + i]; base = i * W
for j in range(m):
ch = row[j]
if ch != 88: # 88 = ma ASCII cua 'X'
c[base + j + 1] = ch - 48
INF = 1 << 60
dist = [INF] * (H * W)
buckets = [[] for _ in range(10)] # Dijkstra voi trong so 0..9: 10 gio vong
left = 0
for j in range(1, m + 1):
v = W + j
if c[v] >= 0:
dist[v] = c[v]; buckets[c[v]].append(v); left += 1
o1 = -W - 1; o2 = -W; o3 = -W + 1; o4 = -1; o5 = 1; o6 = W - 1; o7 = W; o8 = W + 1
offs = (o1, o2, o3, o4, o5, o6, o7, o8)
lo = n * W; hi = lo + W # chi so cac o thuoc hang cuoi
ans = -1
d = 0
while left > 0:
B = buckets[d % 10]
while B:
u = B.pop(); left -= 1
if dist[u] != d: # ban cu, da co duong tot hon
continue
if lo <= u < hi: # cham hang cuoi
ans = d; left = 0
break
for o in offs:
v = u + o
cv = c[v]
if cv >= 0:
nd = d + cv
if nd < dist[v]:
dist[v] = nd; buckets[nd % 10].append(v); left += 1
d += 1
sys.stdout.write("%d\n" % ans)
main()Mô phỏng Dijkstra trên lưới (mỗi bước lấy ra một ô có khoảng cách nhỏ nhất). Cuối cùng đường đi ngắn nhất được tô đậm: đó chính là bức tường đê rẻ nhất.
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (15%) | Sub 2 (20%) | Sub 3 (25%) | Sub 4 (40%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Thử mọi tập ô đê | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – Luồng cực đại (Dinic, tách đỉnh) | Đúng | Đúng | TLE | TLE | 35 |
| Cách 3 – Đối ngẫu + BFS 0-1 (lưới 0/1), còn lại dùng luồng | Đúng | Đúng | Đúng | TLE | 60 |
| Cách 4 – Đối ngẫu + Dijkstra 10 giỏ (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: tường đê chỉ đi 4 hướng (quên nước không đi chéo) | 8/12 | 3/8 | 0/8 | 0/10 | 17,5 |
| Sai: QHĐ theo hàng, tường chỉ đi xuống (thẳng hoặc chéo) | 10/12 | 5/8 | 0/8 | 2/10 | 33 |
| Sai: chỉ đắp một con đê thẳng theo một cột | 7/12 | 3/8 | 0/8 | 0/10 | 16,3 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: bộ test có 38 test (12 + 8 + 8 + 10), mỗi cách ở trên đạt đúng số điểm công bố, còn ba lời giải sai bị bắt như bảng trên. Lời giải chuẩn sol.cpp chạy test lớn nhất ($10^6$ ô) hết khoảng 0,15 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython mất khoảng 3 giây ở lưới $1000 \times 1000$, các em nhớ chọn PyPy 3 khi nộp). Thuật toán luồng (Cách 2) trên lưới $1000 \times 1000$ chạy hơn 20 giây. "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian. Các test lớn đều có đáp án hàng trăm tới hàng chục nghìn công, nhiều "khe chéo" giữa các dải mương và những bức tường đê phải đi ngoằn ngoèo, kể cả đi ngược lên – nên các cách "gần đúng" đều không sống sót!
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét