1 #include2 #include 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 else123 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 } else151 puts("No solution possible");152 }153 return 0;154 }