Kênh rạch (Đề tự luyện HSG Tin 12 – Bài 4)
Đề bài
Kênh rạch. Bản đồ là lưới $R \times C$: # là bờ đất (không vào được), . là nước đứng yên, ^ v < > là nước chảy lên/xuống/trái/phải, S là bến trường, A, B, C, … là nhà của $K$ học trò. Mỗi lần chèo, xuồng sang một ô chung cạnh (trong lưới, không phải bờ đất). Nếu ô đang đứng có dòng chảy và thầy đi đúng hướng dòng chảy của ô đó thì không tốn sức; mọi lần đi khác tốn $1$ đơn vị sức. Thầy Sơn xuất phát từ bến trường, ghé nhà cả $K$ học trò theo thứ tự tùy ý (đi ngang qua nhà cũng tính là đã ghé), rồi quay về bến trường. Tính tổng số đơn vị sức ít nhất.
Dữ liệu vào: dòng đầu $R, C$ ($1 \le R, C \le 300$); $R$ dòng tiếp theo là bản đồ. Đảm bảo có đúng một ô S, $1 \le K \le 15$ và từ bến trường đi được tới mọi nhà.
Kết quả: một số nguyên là tổng số sức ít nhất.
- Subtask 1 (20%): $R, C \le 20$ và $K \le 5$.
- Subtask 2 (25%): $K \le 8$.
- Subtask 3 (25%): bản đồ không có ô nào có dòng chảy.
- Subtask 4 (30%): không có ràng buộc gì thêm.
6 10
.C<<<<<<<<
#......A..
..DB...S##
....>>>>..
...#..#...
.#........9Một cách đi tốn $9$: bến trường → $A$ ($1$) → $C$ ($1$: chèo lên ô có dòng chảy <, nước đẩy xuồng tới tận nhà $C$) → $D$ ($3$) → $B$ ($1$) → bến trường ($3$: xuống, vào dòng chảy >, xuôi ba ô, chèo lên bến). Không có cách nào tốn ít hơn.
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 Kênh rạchLời mở đầu
Bài này thật ra là hai bài toán chồng lên nhau:
- Đi từ điểm này tới điểm kia tốn ít sức nhất là bao nhiêu? Ta chỉ quan tâm tới $K + 1$ "điểm quan trọng": bến trường và $K$ nhà học trò. Gọi $d[i][j]$ là số sức ít nhất để chèo từ điểm $i$ tới điểm $j$.
- Ghé các nhà theo thứ tự nào? Khi đã có bảng $d$, đây là bài toán "người du lịch": chọn thứ tự $p_1, p_2, \dots, p_K$ để $d[S][p_1] + d[p_1][p_2] + \dots + d[p_K][S]$ nhỏ nhất.
Cái bẫy nằm ở chỗ: vì có dòng chảy nên đi và về không tốn như nhau. Trong ví dụ, từ nhà $A$ sang nhà $C$ chỉ tốn $1$ (lên dòng chảy rồi thả trôi), nhưng từ $C$ về $A$ phải chèo ngược dòng, tốn tới $7$:
Từ $A$ sang $C$ rẻ, từ $C$ về $A$ đắt. Vì vậy phải tính BFS xuất phát từ từng điểm, và đi vòng theo chiều nào cũng phải tính riêng.
Mỗi phần có một cách làm "ngây thơ" và một cách làm "xịn", nên mình đi qua 4 cách:
Cách 1Thử mọi thứ tự, mỗi chặng chạy BFS 0-1 – O(K! · K · RC) · 20%
Trước hết cần biết đi từ một ô tới một ô khác tốn ít nhất bao nhiêu sức. Coi mỗi ô nước là một đỉnh; từ ô $u$ có cạnh sang mỗi ô kề $v$, trọng số $0$ nếu $u$ có dòng chảy hướng đúng về $v$, ngược lại trọng số $1$. Đây là đồ thị có hướng (trọng số cạnh $u \to v$ phụ thuộc dòng chảy ở $u$, không phải ở $v$) với trọng số chỉ là $0$ hoặc $1$.
BFS thường không dùng được (cạnh $0$ phá vỡ thứ tự "lớp"), Dijkstra thì dùng được nhưng hơi nặng. Cách gọn nhất là BFS 0-1 với hàng đợi hai đầu (deque):
- Lấy ô $u$ ở đầu hàng đợi.
- Với mỗi ô kề $v$, trọng số $w \in \{0, 1\}$: nếu $dist[u] + w < dist[v]$ thì cập nhật $dist[v]$, rồi đưa $v$ vào đầu hàng đợi nếu $w = 0$, vào cuối nếu $w = 1$.
Nhờ vậy hàng đợi luôn có dạng "vài ô khoảng cách $x$ rồi vài ô khoảng cách $x + 1$" — giống hệt Dijkstra nhưng không cần heap, mỗi ô chỉ xử lý $O(1)$ lần.
Với $K \le 5$ có tối đa $5! = 120$ thứ tự ghé nhà. Thử hết, mỗi thứ tự gọi BFS 0-1 cho từng chặng ($K + 1$ chặng).
#include <bits/stdc++.h>
using namespace std;
int R, C;
vector<string> g;
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
string DIRS = "^v<>";
// 0-1 BFS: sức ít nhất để đi từ ô src tới ô dst
int bfs(int src, int dst) {
vector<int> dist(R * C, INT_MAX);
deque<int> dq;
dist[src] = 0; dq.push_back(src);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
int r = u / C, c = u % C;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#') continue;
int v = nr * C + nc, w = (DIRS.find(g[r][c]) == (size_t)k) ? 0 : 1;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}
}
return dist[dst];
}
int main() {
cin >> R >> C;
g.resize(R);
for (auto &s : g) cin >> s;
int K = 0;
vector<int> pos(16);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (g[i][j] == 'S') pos[0] = i * C + j;
if (g[i][j] >= 'A' && g[i][j] <= 'O') { pos[g[i][j] - 'A' + 1] = i * C + j; K = max(K, g[i][j] - 'A' + 1); }
}
vector<int> p(K);
for (int i = 0; i < K; i++) p[i] = i + 1;
long long best = LLONG_MAX;
do { // thử mọi thứ tự ghé nhà
long long tot = 0;
int at = 0;
for (int i = 0; i <= K && tot < best; i++) {
int to = (i < K) ? p[i] : 0; // cuối cùng quay về trường
tot += bfs(pos[at], pos[to]);
at = to;
}
best = min(best, tot);
} while (next_permutation(p.begin(), p.end()));
cout << best << "\n";
}import sys
from collections import deque
from itertools import permutations
def bfs(g, R, C, src, dst):
# 0-1 BFS: sức ít nhất để đi từ ô src tới ô dst
INF = 10 ** 9
dist = [[INF] * C for _ in range(R)]
dist[src[0]][src[1]] = 0
dq = deque([src])
while dq:
r, c = dq.popleft()
for ch, dr, dc in (('^', -1, 0), ('v', 1, 0), ('<', 0, -1), ('>', 0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] != '#':
w = 0 if g[r][c] == ch else 1
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
if w == 0:
dq.appendleft((nr, nc))
else:
dq.append((nr, nc))
return dist[dst[0]][dst[1]]
def main():
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
g = data[2:2 + R]
pos = {}
for i in range(R):
for j in range(C):
if g[i][j] == 'S' or 'A' <= g[i][j] <= 'O':
pos[g[i][j]] = (i, j)
houses = sorted(x for x in pos if x != 'S')
best = None
for p in permutations(houses): # thử mọi thứ tự ghé nhà
seq = ['S'] + list(p) + ['S']
tot = 0
for i in range(len(seq) - 1):
tot += bfs(g, R, C, pos[seq[i]], pos[seq[i + 1]])
if best is None or tot < best:
best = tot
print(best)
main()Mô phỏng sau chạy BFS 0-1 từ một điểm trên bản đồ ví dụ. Em để ý: khi đi theo dòng chảy (tốn $0$), ô mới được chen lên đầu hàng đợi nên được xét ngay.
Cách 2Tính trước bảng d, rồi thử mọi thứ tự – O(K · RC + K! · K) · 45%
Cách 1 chạy BFS lại rất nhiều lần cho cùng một cặp điểm. Thật ra chỉ có $(K + 1)^2$ cặp điểm quan trọng, và một lần BFS 0-1 xuất phát từ điểm $i$ cho luôn $d[i][j]$ với mọi $j$. Vậy chỉ cần chạy $K + 1$ lần BFS 0-1 để có cả bảng $d$, sau đó mỗi thứ tự ghé nhà chỉ tốn $O(K)$ phép cộng.
Một lỗi hay gặp là chỉ chạy BFS cho nửa số cặp rồi gán $d[j][i] = d[i][j]$ "cho nhanh". Với dòng chảy, $d[A][C] = 1$ nhưng $d[C][A] = 7$ — sai ngay. Phải lấy $d[i][\cdot]$ từ lần BFS xuất phát tại $i$.
Với $K \le 8$: $8! = 40\,320$ thứ tự, quá nhẹ. Nhưng $K = 15$ thì $15! \approx 1{,}3 \cdot 10^{12}$ — không thể.
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<string> g(R);
for (auto &s : g) cin >> s;
int K = 0;
vector<int> pos(16);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (g[i][j] == 'S') pos[0] = i * C + j;
if (g[i][j] >= 'A' && g[i][j] <= 'O') { pos[g[i][j] - 'A' + 1] = i * C + j; K = max(K, g[i][j] - 'A' + 1); }
}
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
string DIRS = "^v<>";
int P = K + 1;
vector<vector<int>> d(P, vector<int>(P));
for (int s = 0; s < P; s++) { // tính trước: 0-1 BFS từ mỗi điểm
vector<int> dist(R * C, INT_MAX);
deque<int> dq;
dist[pos[s]] = 0; dq.push_back(pos[s]);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
int r = u / C, c = u % C;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#') continue;
int v = nr * C + nc, w = (DIRS.find(g[r][c]) == (size_t)k) ? 0 : 1;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}
}
for (int t = 0; t < P; t++) d[s][t] = dist[pos[t]];
}
vector<int> p(K);
for (int i = 0; i < K; i++) p[i] = i + 1;
int best = INT_MAX;
do { // thử mọi thứ tự, mỗi chặng tra bảng d
int tot = d[0][p[0]];
for (int i = 0; i + 1 < K; i++) tot += d[p[i]][p[i + 1]];
tot += d[p[K - 1]][0];
best = min(best, tot);
} while (next_permutation(p.begin(), p.end()));
cout << best << "\n";
}import sys
from collections import deque
from itertools import permutations
def main():
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
g = data[2:2 + R]
pos = [None] * 16
K = 0
for i in range(R):
for j in range(C):
ch = g[i][j]
if ch == 'S':
pos[0] = (i, j)
elif 'A' <= ch <= 'O':
pos[ord(ch) - 64] = (i, j)
K = max(K, ord(ch) - 64)
P = K + 1
INF = 10 ** 9
d = [[0] * P for _ in range(P)]
for s in range(P): # tính trước: 0-1 BFS từ mỗi điểm
dist = [[INF] * C for _ in range(R)]
dist[pos[s][0]][pos[s][1]] = 0
dq = deque([pos[s]])
while dq:
r, c = dq.popleft()
for ch, dr, dc in (('^', -1, 0), ('v', 1, 0), ('<', 0, -1), ('>', 0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] != '#':
w = 0 if g[r][c] == ch else 1
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
if w == 0:
dq.appendleft((nr, nc))
else:
dq.append((nr, nc))
for t in range(P):
d[s][t] = dist[pos[t][0]][pos[t][1]]
best = INF
for p in permutations(range(1, P)): # thử mọi thứ tự, mỗi chặng tra bảng d
tot = d[0][p[0]] + d[p[-1]][0]
for i in range(K - 1):
tot += d[p[i]][p[i + 1]]
best = min(best, tot)
print(best)
main()Cách 3Không có dòng chảy: BFS thường + QHĐ bitmask – O(K · RC + 2^K · K²) · 25%
Subtask 3 không có dòng chảy: mỗi bước tốn đúng $1$, nên $d[i][j]$ tính bằng BFS thường. Phần khó là $K = 15$: không thử hết hoán vị được. Nhận xét then chốt:
Khi đã ghé tập nhà $T$ và đang đứng ở nhà $j$, chi phí cho phần còn lại của hành trình không phụ thuộc thứ tự đã ghé các nhà trong $T$. Vậy hai hành trình cùng $(T, j)$ chỉ cần giữ cái rẻ hơn. Có $2^K \cdot K$ trạng thái như vậy — với $K = 15$ chỉ cỡ $5 \cdot 10^5$.
Biểu diễn tập $T$ bằng một số nguyên mask (bit $j - 1$ bật nếu đã ghé nhà thứ $j$). Gọi $dp[mask][j]$ là số sức ít nhất để từ bến trường đi ghé đúng các nhà trong mask và đang đứng ở nhà $j$ (nhà $j$ thuộc mask):
- Khởi tạo: $dp[\{j\}][j] = d[S][j]$.
- Chuyển trạng thái: từ $(mask, j)$ đi tiếp tới nhà $t \notin mask$: $dp[mask \cup \{t\}][t] \leftarrow \min(\dots,\ dp[mask][j] + d[j][t])$.
- Đáp án: $\min_j \big(dp[\text{full}][j] + d[j][S]\big)$ — nhớ cộng chặng quay về bến trường.
Duyệt mask tăng dần là đúng thứ tự, vì mask $\cup \{t\}$ luôn lớn hơn mask. Số phép tính: $2^K \cdot K \cdot K \approx 7{,}4 \cdot 10^6$ với $K = 15$.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
int R, C;
cin >> R >> C;
vector<string> g(R);
for (auto &s : g) cin >> s;
int K = 0;
vector<int> pos(16);
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (g[i][j] == 'S') pos[0] = i * C + j;
if (g[i][j] >= 'A' && g[i][j] <= 'O') { pos[g[i][j] - 'A' + 1] = i * C + j; K = max(K, g[i][j] - 'A' + 1); }
}
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
int P = K + 1;
vector<vector<int>> d(P, vector<int>(P));
for (int s = 0; s < P; s++) { // BFS thường: mỗi bước tốn 1 (không có dòng chảy)
vector<int> dist(R * C, INF);
queue<int> q;
dist[pos[s]] = 0; q.push(pos[s]);
while (!q.empty()) {
int u = q.front(); q.pop();
int r = u / C, c = u % C;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#') continue;
int v = nr * C + nc;
if (dist[v] == INF) { dist[v] = dist[u] + 1; q.push(v); }
}
}
for (int t = 0; t < P; t++) d[s][t] = dist[pos[t]];
}
int full = (1 << K) - 1;
vector<vector<int>> dp(full + 1, vector<int>(P, INF));
for (int j = 1; j < P; j++) dp[1 << (j - 1)][j] = d[0][j];
for (int mask = 1; mask <= full; mask++)
for (int j = 1; j < P; j++) {
if (dp[mask][j] >= INF) continue;
for (int t = 1; t < P; t++) {
if (mask >> (t - 1) & 1) continue;
int nm = mask | (1 << (t - 1));
dp[nm][t] = min(dp[nm][t], dp[mask][j] + d[j][t]);
}
}
int ans = INF;
for (int j = 1; j < P; j++) ans = min(ans, dp[full][j] + d[j][0]);
cout << ans << "\n";
}import sys
from collections import deque
def main():
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1])
g = data[2:2 + R]
pos = [None] * 16
K = 0
for i in range(R):
for j in range(C):
ch = g[i][j]
if ch == 'S':
pos[0] = (i, j)
elif 'A' <= ch <= 'O':
pos[ord(ch) - 64] = (i, j)
K = max(K, ord(ch) - 64)
P = K + 1
INF = 10 ** 9
d = [[0] * P for _ in range(P)]
for s in range(P): # BFS thường: mỗi bước tốn 1
dist = [[INF] * C for _ in range(R)]
dist[pos[s][0]][pos[s][1]] = 0
q = deque([pos[s]])
while q:
r, c = q.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and g[nr][nc] != '#' and dist[nr][nc] == INF:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
for t in range(P):
d[s][t] = dist[pos[t][0]][pos[t][1]]
full = (1 << K) - 1
dp = [[INF] * P for _ in range(full + 1)]
for j in range(1, P):
dp[1 << (j - 1)][j] = d[0][j]
for mask in range(1, full + 1):
row = dp[mask]
for j in range(1, P):
if row[j] >= INF:
continue
for t in range(1, P):
if mask >> (t - 1) & 1:
continue
nm = mask | (1 << (t - 1))
if row[j] + d[j][t] < dp[nm][t]:
dp[nm][t] = row[j] + d[j][t]
print(min(dp[full][j] + d[j][0] for j in range(1, P)))
main()Mô phỏng QHĐ bitmask (bảng $d$ được tính bằng BFS 0-1 như Cách 4). Mỗi bước lấy một trạng thái $(mask, j)$ và "đẩy" sang các nhà chưa ghé:
Cách 4BFS 0-1 từ từng điểm + QHĐ bitmask – O(K · RC + 2^K · K²) · 100%
Ghép hai mảnh lại: bảng $d$ tính bằng BFS 0-1 xuất phát từ mỗi điểm trong $K + 1$ điểm quan trọng (Cách 2), thứ tự ghé nhà giải bằng QHĐ bitmask (Cách 3). Tổng cộng khoảng $16 \cdot 9 \cdot 10^4 \cdot 4 \approx 5{,}8 \cdot 10^6$ thao tác cho phần BFS và $7{,}4 \cdot 10^6$ cho phần QHĐ.
Nếu đường đi ngắn nhất từ $i$ tới $j$ đi ngang qua nhà $t$, thì có một thứ tự khác "dừng" ở $t$ giữa đường với cùng tổng chi phí (vì $d[i][t] + d[t][j] \le$ chi phí đoạn đó). QHĐ đã xét mọi thứ tự nên không bỏ sót phương án nào. Bộ brute của mình (BFS trên trạng thái (ô, tập nhà đã ghé)) cũng xác nhận điều này trên 600 test ngẫu nhiên.
Bản Python giữ đúng ý tưởng nhưng viết "kiểu Python" cho nhanh: BFS 0-1 được làm theo từng mức sức $0, 1, 2, \dots$ (ô đi theo dòng chảy được nối vào cuối danh sách mức hiện tại, ô tốn thêm 1 vào danh sách mức sau) và dừng sớm khi đã gặp đủ $K + 1$ điểm; QHĐ viết dạng "kéo": $dp[mask][j] = \min_i \big(dp[mask \setminus \{j\}][i] + d[i][j]\big)$ tính bằng min(map(add, ...)).
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main() {
int R, C;
scanf("%d %d", &R, &C);
vector<string> g(R);
char buf[1005];
for (int i = 0; i < R; i++) { scanf("%s", buf); g[i] = buf; }
int n = R * C, K = 0;
vector<int> pos(16, -1); // pos[0] = trường S, pos[1..K] = nhà A, B, ...
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
char ch = g[i][j];
if (ch == 'S') pos[0] = i * C + j;
else if (ch >= 'A' && ch <= 'O') { pos[ch - 'A' + 1] = i * C + j; K = max(K, ch - 'A' + 1); }
}
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
const string DIRS = "^v<>";
int P = K + 1;
vector<vector<int>> d(P, vector<int>(P)); // d[i][j]: sức ít nhất để đi từ điểm i tới điểm j
vector<int> dist(n);
deque<int> dq;
for (int s = 0; s < P; s++) { // 0-1 BFS từ mỗi điểm đặc biệt
fill(dist.begin(), dist.end(), INF);
dist[pos[s]] = 0; dq.push_back(pos[s]);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
int r = u / C, c = u % C;
int fl = (int)DIRS.find(g[r][c]); // hướng dòng chảy ở ô u (-1 nếu nước đứng)
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#') continue;
int v = nr * C + nc, w = (k == fl) ? 0 : 1;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}
}
for (int t = 0; t < P; t++) d[s][t] = dist[pos[t]];
}
// dp[mask][j]: đã ghé tập nhà mask (bit j-1 = nhà j), đang ở nhà j
int full = (1 << K) - 1;
vector<int> dp((size_t)(full + 1) * P, INF);
for (int j = 1; j < P; j++) dp[(size_t)(1 << (j - 1)) * P + j] = d[0][j];
for (int mask = 1; mask <= full; mask++)
for (int j = 1; j < P; j++) {
int cur = dp[(size_t)mask * P + j];
if (cur >= INF) continue;
for (int t = 1; t < P; t++) {
if (mask >> (t - 1) & 1) continue;
int nm = mask | (1 << (t - 1));
int val = cur + d[j][t];
if (val < dp[(size_t)nm * P + t]) dp[(size_t)nm * P + t] = val;
}
}
int ans = INF;
for (int j = 1; j < P; j++) ans = min(ans, dp[(size_t)full * P + j] + d[j][0]);
printf("%d\n", ans);
return 0;
}import sys
from operator import add
def main():
data = sys.stdin.buffer.read().split()
R = int(data[0]); C = int(data[1])
W = C + 2 # lưới có viền đất bao quanh
N = (R + 2) * W
ok = [False] * N # ô đi được (không phải đất)
zero = [-1] * N # ô kề theo dòng chảy (đi không tốn sức)
pos = [-1] * 16
K = 0
step = {94: -W, 118: W, 60: -1, 62: 1} # ^ v < >
for i in range(R):
row = data[2 + i]
base = (i + 1) * W + 1
for j in range(C):
ch = row[j]
if ch == 35: # '#'
continue
u = base + j
ok[u] = True
if ch in step:
zero[u] = u + step[ch]
elif ch == 83: # 'S'
pos[0] = u
elif 65 <= ch <= 79: # 'A'..'O'
pos[ch - 64] = u
if ch - 64 > K:
K = ch - 64
for u in range(N): # dòng chảy hướng vào đất thì coi như không có
z = zero[u]
if z >= 0 and not ok[z]:
zero[u] = -1
P = K + 1
INF = 10 ** 9
isT = [-1] * N
for t in range(P):
isT[pos[t]] = t
d = [[INF] * P for _ in range(P)]
for s in range(P): # 0-1 BFS theo từng mức sức d
dist = [INF] * N
src = pos[s]
dist[src] = 0
cur = [src]
lev = 0
left = P
ds = d[s]
while cur and left:
nxt = []
l1 = lev + 1
for u in cur: # cur có thể dài thêm trong lúc duyệt
if dist[u] != lev:
continue
t = isT[u]
if t >= 0:
ds[t] = lev
left -= 1
if not left:
break
z = zero[u]
if z >= 0 and dist[z] > lev:
dist[z] = lev
cur.append(z)
v = u - W
if ok[v] and dist[v] > l1:
dist[v] = l1; nxt.append(v)
v = u + W
if ok[v] and dist[v] > l1:
dist[v] = l1; nxt.append(v)
v = u - 1
if ok[v] and dist[v] > l1:
dist[v] = l1; nxt.append(v)
v = u + 1
if ok[v] and dist[v] > l1:
dist[v] = l1; nxt.append(v)
cur = nxt
lev = l1
# dp[mask][j]: đã ghé tập nhà mask, đang ở nhà j (cột 0 không dùng)
full = (1 << K) - 1
col = [[d[i][j] for i in range(P)] for j in range(P)] # col[j][i] = d[i][j]
infrow = [INF] * P
dp = [infrow] * (full + 1)
for j in range(1, P):
row = [INF] * P
row[j] = d[0][j]
dp[1 << (j - 1)] = row
for mask in range(1, full + 1):
if mask & (mask - 1) == 0:
continue
row = [INF] * P
m = mask
while m:
b = m & -m
m ^= b
j = b.bit_length()
row[j] = min(map(add, dp[mask ^ b], col[j]))
dp[mask] = row
last = dp[full]
ans = min(last[j] + d[j][0] for j in range(1, P))
sys.stdout.write(str(ans) + "\n")
main()Với BFS thường, ta hay đánh dấu ô ngay khi đẩy vào hàng đợi. Với BFS 0-1 làm vậy là sai: một ô có thể được tìm thấy trước qua cạnh $1$, rồi sau đó mới tìm ra đường rẻ hơn qua dòng chảy (cạnh $0$). Phải dùng điều kiện "$dist[u] + w < dist[v]$" và cho phép cập nhật lại.
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – thử mọi thứ tự, BFS 0-1 từng chặng | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – tính trước bảng d, thử mọi hoán vị | Đúng | Đúng | TLE | TLE | 45 |
| Cách 3 – BFS thường (bỏ qua dòng chảy) + bitmask | 0/8 | 0/8 | Đúng | 0/10 | 25 |
| Cách 4 – BFS 0-1 + QHĐ bitmask (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: BFS 0-1 nhưng chốt khoảng cách ngay lần đầu gặp ô | 6/8 | 0/8 | Đúng | 1/10 | 43 |
| Sai: coi $d[i][j] = d[j][i]$ (chỉ BFS một nửa số cặp) | 2/8 | 0/8 | Đúng | 0/10 | 30 |
| Sai: tham lam – luôn tới nhà gần nhất chưa ghé | 4/8 | 0/8 | 1/8 | 0/10 | 13,12 |
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: 34 test (subtask 1: 8 test, subtask 2: 8 test, subtask 3: 8 test, subtask 4: 10 test), chấm kiểu "đúng test nào được điểm test đó". Mọi test của subtask 2–4 có lưới cỡ $250$–$300$ hàng và cột (vài test là con kênh dài $1 \times 300$, $2 \times 300$ hoặc $300 \times 2$); subtask 2 có $K = 7$ hoặc $8$, subtask 3–4 có $K = 13$ tới $15$. Bản đồ có đủ kiểu: mặt nước có dòng chảy ngẫu nhiên, các "dòng sông" dài uốn khúc, mê cung kênh rạch mà nước chảy về một cửa sông, các làn nước chảy ngược chiều nhau ngăn bởi bờ đất — để khoảng cách hai chiều lệch nhau thật nhiều. Lời giải chuẩn C++ chạy dưới 0,25 giây. Bản Python nên nộp bằng PyPy 3 (giới hạn 3 giây).
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