UVA_387

    由于是精确覆盖问题，所以可以用Dancing Links去解决，只是需要把每个拼图按摆放位置的不同分成若干个拼图，但这些拼图都属于一类的，这一点要在Dancing Links的列中体现出来。

#include
     
       #include
      
        #define MAXM 6 #define INF 0x3f3f3f3f const int MAXN = 6 * 6; const int MAXD = 6 * 6 * 6 * (6 * 6 + 6) + 6 * 6 + 6; char b[MAXM]; int N = 4, M, ans[MAXM][MAXM], g[MAXM][MAXM][MAXM], x[MAXM], y[MAXM]; int size, U[MAXD], D[MAXD], L[MAXD], R[MAXD], S[MAXN], H[MAXD], X[MAXD], C[MAXD], Q[MAXD]; int st[MAXD], sx[MAXD], sy[MAXD]; void prepare(int r, int c) {
   int i; for(i = 0; i <= c; i ++)     {
           L[i + 1] = i, R[i] = i + 1;         S[i] = 0;         U[i] = D[i] = i;     }     R[c] = 0;     size = c; while(r)         H[r --] = -1; } void insert(int r, int c) {
       ++ size;     X[size] = r;     C[size] = c;     ++ S[c];     U[size] = c;     D[size] = D[c];     U[D[c]] = size;     D[c] = size; if(H[r] == -1)         H[r] = L[size] = R[size] = size; else     {
           R[size] = R[H[r]];         L[size] = H[r];         L[R[H[r]]] = size;         R[H[r]] = size;     } } void init() {
   int i, j, k, p, q, row;     prepare(N * N * M, N * N + M);     row = 0; for(i = 1; i <= M; i ++)     {
           scanf("%d%d", &x[i], &y[i]); for(j = 0; j < x[i]; j ++)         {
               scanf("%s", b); for(k = 0; k < y[i]; k ++)                 g[i][j][k] = b[k] - '0';         } for(j = 0; j + x[i] <= N; j ++) for(k = 0; k + y[i] <= N; k ++)             {
                   ++ row;                 st[row] = i, sx[row] = j, sy[row] = k;                 insert(row , i); for(p = 0; p < x[i]; p ++) for(q = 0; q < y[i]; q ++) if(g[i][p][q])                             insert(row, (j + p) * N + (k + q) + M + 1);             }     } } void remove(int c) {
   int i, j;     L[R[c]] = L[c];     R[L[c]] = R[c]; for(i = D[c]; i != c; i = D[i]) for(j = R[i]; j != i; j = R[j])         {
               U[D[j]] = U[j];             D[U[j]] = D[j];         } } void resume(int c) {
   int i, j; for(i = U[c]; i != c; i = U[i]) for(j = L[i]; j != i; j = L[j])         {
               U[D[j]] = j;             D[U[j]] = j;         }     L[R[c]] = c;     R[L[c]] = c; } int dance(int cur) {
   int i, j, min, c; if(!R[0])     {
   int k, row, p, q; for(i = 0; i < cur; i ++)         {
               row = Q[i];             k = st[row]; for(p = 0; p < x[k]; p ++) for(q = 0; q < y[k]; q ++) if(g[k][p][q])                         ans[p + sx[row]][q + sy[row]] = k;         } return 1;     }     min = INF; for(i = R[0]; i != 0; i = R[i]) if(S[i] < min)         {
               min = S[i];             c = i;         }     remove(c); for(i = D[c]; i != c; i = D[i])     {
           Q[cur] = X[i]; for(j = R[i]; j != i; j = R[j])             remove(C[j]); if(dance(cur + 1)) return 1; for(j = L[i]; j != i; j = L[j])             resume(C[j]);     }     resume(c); return 0; } void solve() {
   int i, j; if(dance(0))     {
   for(i = 0; i < N; i ++)         {
   for(j = 0; j < N; j ++)                 printf("%d", ans[i][j]);             printf("\n");         }     } else         printf("No solution possible\n"); } int main() {
   int t = 0; for(;;)     {
           scanf("%d", &M); if(!M) break; if(t ++)             printf("\n");         init();         solve();     } return 0; }