Cách giải đối với dạng bài này là nén lưới ô vuông 10⁹ x 10⁹ về lưới ô vuông 2N x 2N (N: 1..1000). Lời khuyên cho dạng bài này là: trên lưới ban đầu, dùng định nghĩa điểm thay vì ô. Trên lưới sau khi nén, dùng định nghĩa ô thay vì điểm.
Đề bài
Có N bức tường (N: 0..1000) có dạng hình chữ nhật nằm trên lưới ô vuông P x Q ô (P, Q: 1..10⁶). Một con rô bốt ở ô (x, y) có thể đi đến ô (x+1, y) và (x, y+1) miễn là ô nguồn và ô đích không có tường. Đếm số ô (x, y) không phải tường và rô bốt tại (x, y) không thể đi đến ô (P, Q).
Độ phức tạp
O(N²)
Code này của Nguyễn Tiến Trung Kiên
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define all(a) a.begin(), a.end()
struct separator_list {
vector<int> a;
void insert(int x)
{ a.push_back(x); }
void ready()
{ sort(all(a)); a.erase(unique(all(a)), a.end()); }
int index(int x)
{ return lower_bound(all(a), x) - a.begin(); }
} xs, ys; //
struct worker {
static const int N = 3003;
int m, n, a[N][N];
bool F[N][N];
void init(int _m, int _n)
{ m=_m; n=_n; }
void done() {
for (int i=0; i<=m+1; i++)
for (int j=0; j<=n+1; j++) {
a[i][j] = 0;
F[i][j] = false;
}
}
void fill(int x, int y, int u, int v) {
u++; v++;
a[x][y]++; a[x][v]--;
a[u][y]--; a[u][v]++;
}
void ready() {
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
}
long solve(const vector<int> &xs, const vector<int> &ys) {
for (int i=m; i>=1; i--)
for (int j=n; j>=1; j--)
if (a[i][j])
F[i][j] = false;
else if (i==m && j==n)
F[i][j] = true;
else
F[i][j] = i<m && F[i+1][j] || j<n && F[i][j+1];
long v0 = 0;
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
if (!a[i][j] && !F[i][j])
v0 += 1LL * (xs[i]-xs[i-1]) * (ys[j] - ys[j-1]);
return v0;
}
} W; //
const int N = 1003;
int xh, yh, n;
tuple<int, int, int, int> Rect[N];
void solve(int t) {
scanf("%d%d%d", &yh, &xh, &n);
if (xh==0 && yh==0 && n==0) exit(0);
xs.insert(0); xs.insert(xh);
ys.insert(0); ys.insert(yh);
for (int i=1; i<=n; i++) {
int x, y; scanf("%d%d", &x, &y);
int u, v; scanf("%d%d", &u, &v); u++; v++;
Rect[i] = make_tuple(x, y, u, v);
xs.insert(x); ys.insert(y);
xs.insert(u); ys.insert(v);
}
xs.ready(); ys.ready();
W.init(xs.index(xh), ys.index(yh));
for (int i=1; i<=n; i++) {
int x, y, u, v; tie(x, y, u, v) = Rect[i];
W.fill(xs.index(x+1), ys.index(y+1), xs.index(u), ys.index(v));
}
W.ready();
printf("Case %d: %lld\n", t, W.solve(xs.a, ys.a));
}
int main() {
for (int i=1; true; i++) {
solve(i);
xs.a.clear();
ys.a.clear();
W.done();
}
}
Nhận xét
Bài này đã được dùng để nộp cho một bài trên UVa.
Tham khảo
https://uva.onlinejudge.org/external/10/1092.pdf