http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531
蟻本p.150とほぼ同じ問題。蟻本みながら実装。
座標圧縮して実際にタイル作って連続するテープが貼られていない領域の数を求めた。
1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5 #include <queue>
6 using namespace std;
7
8 #define MAX_N 1001
9
10 struct S {
11 int y, x;
12 S(int y, int x) : y(y), x(x) {}
13 };
14
15 const int dy[] = {0, 1, 0, -1},
16 dx[] = {1, 0, -1, 0};
17
18 int W, H, N;
19 int X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N];
20
21 int compress(int *x1, int *x2, int w) {
22 vector<int> xs;
23 for (int i = 0; i < N; i++) {
24 if (x1[i] - 1 >= 0) xs.push_back(x1[i] - 1);
25 xs.push_back(x1[i]);
26 xs.push_back(x2[i] - 1);
27 if (x2[i] < w) xs.push_back(x2[i]);
28 }
29 sort(xs.begin(), xs.end());
30 xs.erase(unique(xs.begin(), xs.end()), xs.end());
31 for (int i = 0; i < N; i++) {
32 x1[i] = lower_bound(xs.begin(), xs.end(), x1[i]) - xs.begin();
33 x2[i] = lower_bound(xs.begin(), xs.end(), x2[i]) - xs.begin();
34 }
35 return xs.size();
36 }
37
38 int main() {
39 while (scanf("%d %d", &W, &H), W || H) {
40 scanf("%d", &N);
41 for (int i = 0; i < N; i++) {
42 scanf("%d %d %d %d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
43 }
44 int w = compress(X1, X2, W);
45 int h = compress(Y1, Y2, H);
46
47 bool F[h][w]; memset(F, 0, sizeof(F));
48 for (int n = 0; n < N; n++) {
49 for (int i = Y1[n]; i < Y2[n]; i++) {
50 for (int j = X1[n]; j < X2[n]; j++) {
51 F[i][j] = true;
52 }
53 }
54 }
55
56 bool used[h][w]; memset(used, 0, sizeof(used));
57 int cnt = 0;
58 for (int y = 0; y < h; y++) {
59 for (int x = 0; x < w; x++) {
60 if (!used[y][x] && !F[y][x]) {
61 cnt++;
62 used[y][x] = true;
63 queue<S> q; q.push(S(y, x));
64 while (!q.empty()) {
65 S s = q.front(); q.pop();
66 for (int i = 0; i < 4; i++) {
67 int ny = s.y + dy[i], nx = s.x + dx[i];
68 if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
69 if (!used[ny][nx] && !F[ny][nx]) {
70 used[ny][nx] = true;
71 q.push(S(ny, nx));
72 }
73 }
74 }
75 }
76 }
77 }
78
79 printf("%d\n", cnt);
80 }
81 return 0;
82 }