Hướng dẫn giải của [Free Contest 01] ASCII
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Yêu cầu: tính diện tích đa giác được vẽ bằng các ký tự ~.~, ~/~ và ~\\~ trong lưới ~M \cdot N~.
Sub 1: Tìm cạnh bằng cách quét lưới — ~O((MN)^2)~, dùng khi ~M \cdot N \le 400~
Mỗi ô ~/~ hoặc ~\\~ là một cạnh nối hai đỉnh nguyên của lưới. Đi theo đường đa giác, mỗi bước quét toàn bộ lưới để tìm cạnh tiếp theo. Diện tích tính bằng công thức dây giày (shoelace).
Nếu chỉ nộp sub này: đúng 31/31 test.
Sub 2: Danh sách kề — ~O(MN)~
Mỗi đỉnh nguyên có đúng hai cạnh trên đa giác, nên lưu danh sách kề và đi theo đường đa giác trong thời gian tuyến tính. Cộng dồn công thức shoelace và chia 2 ở cuối.
Nếu chỉ nộp sub này: đúng 31/31 test.
Chương trình hoàn chỉnh
Với ~M \cdot N \le 400~ gọi sub 1, còn lại gọi sub 2. 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;
int M, N;
vector<string> g; // g[r][c]: ký tự ô hàng r, cột c ('.', '/', '\')
// Đỉnh là điểm nguyên (r, c), 0 <= r <= M, 0 <= c <= N.
// Ô '/' là đoạn (r+1,c)-(r,c+1); ô '\' là đoạn (r,c)-(r+1,c+1).
// Diện tích tính bằng công thức dây giày (shoelace) trên đường đa giác.
// Sub 1: tìm cạnh kế tiếp bằng cách quét mọi ô, O((MN)^2) — dùng khi M*N <= 400
struct Edge { int r1, c1, r2, c2; bool used; };
void sub1() {
vector<Edge> es;
for (int r = 0; r < M; r++)
for (int c = 0; c < N; c++) {
if (g[r][c] == '/') es.push_back({r + 1, c, r, c + 1, false});
else if (g[r][c] == '\\') es.push_back({r, c, r + 1, c + 1, false});
}
long long total = 0;
for (size_t s = 0; s < es.size(); s++) {
if (es[s].used) continue;
es[s].used = true;
int sr = es[s].r1, sc = es[s].c1;
int cr = es[s].r2, cc = es[s].c2;
long long sum = (long long)sc * cr - (long long)cc * sr; // toạ độ (x=c, y=r)
while (!(cr == sr && cc == sc)) {
bool found = false;
for (auto &e : es) {
if (e.used) continue;
int nr, nc;
if (e.r1 == cr && e.c1 == cc) { nr = e.r2; nc = e.c2; }
else if (e.r2 == cr && e.c2 == cc) { nr = e.r1; nc = e.c1; }
else continue;
e.used = true;
sum += (long long)cc * nr - (long long)nc * cr;
cr = nr; cc = nc;
found = true;
break;
}
if (!found) break;
}
total += llabs(sum);
}
cout << total / 2 << "\n";
}
// Sub 2: danh sách kề, đi theo đường đa giác O(MN) — lời giải đầy đủ
void sub2() {
int W = N + 1;
int P = (M + 1) * W;
vector<vector<int>> adj(P);
auto link = [&](int p, int q) { adj[p].push_back(q); adj[q].push_back(p); };
for (int r = 0; r < M; r++)
for (int c = 0; c < N; c++) {
if (g[r][c] == '/') link((r + 1) * W + c, r * W + c + 1);
else if (g[r][c] == '\\') link(r * W + c, (r + 1) * W + c + 1);
}
vector<char> vis(P, 0);
long long total = 0;
for (int s = 0; s < P; s++) {
if (vis[s] || adj[s].empty()) continue;
long long sum = 0;
int prev = -1, cur = s;
while (true) {
vis[cur] = 1;
// mỗi đỉnh trên đường đa giác có đúng 2 cạnh; đi theo cạnh không quay lại
int nxt = (adj[cur][0] != prev) ? adj[cur][0] : adj[cur][1];
long long cr = cur / W, cc = cur % W, nr = nxt / W, nc = nxt % W;
sum += cc * nr - nc * cr;
prev = cur;
cur = nxt;
if (cur == s) break;
}
total += llabs(sum);
}
cout << total / 2 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> M >> N;
g.resize(M);
for (auto &row : g) cin >> row;
if (M * N <= 400) sub1();
else sub2();
return 0;
}
Bình luận