【UVa】387 A Puzzling Problem

  1 #include<cstdio>
  2 #include<cstring>
  3 #define MAXM 10
  4 #define MAXN 100000
  5 #define MAXL 110
  6 #define INF 0x7FFFFFFF
  7 struct node {
  8     int h, l;
  9     char s[MAXM][MAXM];
 10 };
 11 struct answer {
 12     int pos, h, l;
 13 };
 14 answer ans[MAXL];
 15 node sq[MAXM];
 16 bool vis[MAXL];
 17 int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
 18 int H[MAXN], S[MAXN], C[MAXN], X[MAXN];
 19 int size;
 20 char a[MAXM][MAXM];
 21 void Init(int m) {
 22     int i;
 23     memset(vis, false, sizeof(vis));
 24     for (i = 0; i <= m; i++) {
 25         L[i + 1] = i;
 26         R[i] = i + 1;
 27         U[i] = D[i] = i;
 28         S[i] = 0;
 29     }
 30     R[m] = 0;
 31     size = m + 1;
 32 }
 33 void Link(int r, int c) {
 34     U[size] = c;
 35     D[size] = D[c];
 36     U[D[c]] = size;
 37     D[c] = size;
 38     if (H[r] < 0)
 39         H[r] = L[size] = R[size] = size;
 40     else {
 41         L[size] = H[r];
 42         R[size] = R[H[r]];
 43         L[R[H[r]]] = size;
 44         R[H[r]] = size;
 45     }
 46     S[c]++;
 47     X[size] = r;
 48     C[size++] = c;
 49 }
 50 void Remove(int c) {
 51     int i, j;
 52     L[R[c]] = L[c];
 53     R[L[c]] = R[c];
 54     for (i = D[c]; i != c; i = D[i]) {
 55         for (j = R[i]; j != i; j = R[j]) {
 56             U[D[j]] = U[j];
 57             D[U[j]] = D[j];
 58             S[C[j]]--;
 59         }
 60     }
 61 }
 62 void Resume(int c) {
 63     int i, j;
 64     L[R[c]] = R[L[c]] = c;
 65     for (i = D[c]; i != c; i = D[i]) {
 66         for (j = R[i]; j != i; j = R[j]) {
 67             U[D[j]] = D[U[j]] = j;
 68             S[C[j]]++;
 69         }
 70     }
 71 }
 72 bool Dance() {
 73     if (R[0] == 0)
 74         return true;
 75     int i, j, temp, c;
 76     for (temp = INF,i = R[0]; i; i = R[i]) {
 77         if (temp > S[i]) {
 78             temp = S[i];
 79             c = i;
 80         }
 81     }
 82     Remove(c);
 83     for (i = D[c]; i != c; i = D[i]) {
 84         vis[X[i]] = true;
 85         for (j = R[i]; j != i; j = R[j])
 86             Remove(C[j]);
 87         if (Dance())
 88             return true;
 89         for (j = L[i]; j != i; j = L[j])
 90             Resume(C[j]);
 91         vis[X[i]] = false;
 92     }
 93     Resume(c);
 94     return false;
 95 }
 96 void Build(int n) {
 97     int i, j, k, t, p, r;
 98     for (i = r = 0; i < n; i++) {
 99         for (j = 0; j <= 4 - sq[i].h; j++) {
100             for (k = 0; k <= 4 - sq[i].l; k++) {
101                 H[++r] = -1;
102                 Link(r, 16 + i + 1);
103                 ans[r].pos = i;
104                 ans[r].h = j;
105                 ans[r].l = k;
106                 for (t = 0; t < sq[i].h; t++) {
107                     for (p = 0; p < sq[i].l; p++) {
108                         if (sq[i].s[t][p] != '0')
109                             Link(r, 4 * (j + t) + k + p + 1);
110                     }
111                 }
112             }
113         }
114     }
115 }
116 int main() {
117     int n, i, j, k;
118     bool flag = true;
119     while (scanf("%d", &n), n) {
120         if (flag)
121             flag = false;
122         else
123             putchar('\n');
124         Init(16 + n);
125         for (i = 0; i < n; i++) {
126             scanf("%d%d", &sq[i].h, &sq[i].l);
127             for (j = 0; j < sq[i].h; j++) {
128                 for (k = 0; k < sq[i].l; k++)
129                     scanf(" %c", &sq[i].s[j][k]);
130             }
131         }
132         Build(n);
133         if (Dance()) {
134             for (i = 1; i < MAXL; i++) {
135                 if (vis[i]) {
136                     for (j = 0; j < sq[ans[i].pos].h; j++) {
137                         for (k = 0; k < sq[ans[i].pos].l; k++) {
138                             if (sq[ans[i].pos].s[j][k] != '0')
139                                 a[j + ans[i].h][k + ans[i].l] = '1'
140                                         + ans[i].pos;
141                         }
142                     }
143                 }
144             }
145             for (i = 0; i < 4; i++) {
146                 for (j = 0; j < 4; j++)
147                     putchar(a[i][j]);
148                 putchar('\n');
149             }
150         } else
151             puts("No solution possible");
152     }
153     return 0;
154 }