ログイン
編集不可のページディスカッション情報添付ファイル
iz/競技プログラミング/AOJ 0531 Paint Color

MMA

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 }

iz/競技プログラミング/AOJ 0531 Paint Color (最終更新日時 2012-12-30 16:52:06 更新者 iz)