解題區/解題區 - UVa

UVa 745 - Numeric Puzzles Again

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定七巧板拼圖，保證每一個拼圖都會在最後的盤面上，並且每一個拼圖不可旋轉。

但是在輸出的時候，選擇一個最大權重的表示法進行輸出，同時每組測資保證最多一種同構解。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
7
6
3333
33
3333
 33
 33
7  7
7  7
7777
88888
 6
666
 66
  22
222
  2
  5
 55
 55
555
5 5
#
0

Sample Output

1
2
3
4
5
6
7
8777333
8733333
8733323
8777323
8655222
6665552
6655555

Solution

轉換成精準覆蓋問題，套用 DLX 做法來完成。

特別小心輸出的表示法，計算權重時，有可能會有嚴重的 overflow，可以用大數比大小、或者 double 來完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
char pattern[32][4][32][32]; // [id][rotate][x][y]
char prob_out[4][32][32], out[32][32];
int n, m;
int mx[30];
void out_update() {
    int mxrt = -1;
    for (int rt = 1; rt < 4; rt++) {
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++) {
                prob_out[rt][p][q] = prob_out[rt-1][q][n - 1 - p];
            }
        }
    }
    for (int rt = 0; rt < 4; rt++) {
        int sum[30] = {};
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++)
                sum[q] += prob_out[rt][p][n - q - 1] - '0';
        }
        for (int p = 0; p < 29; p++)
            sum[p+1] += sum[p]/10, sum[p] %= 10;
        int flag = 0;
        for (int p = 29; p >= 0; p--) {
            if (sum[p] != mx[p]) {
                flag = sum[p] > mx[p] ? 1 : -1;
                break;
            }
        }
        if (flag == 1) {
            for (int p = 29; p >= 0; p--)
                mx[p] = sum[p];
            mxrt = rt;
        }
    }
    if (mxrt >= 0) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) 
                out[i][j] = prob_out[mxrt][i][j];
    }
}
class DLX {
    public:
    struct DancingLinks {
        int left, right, up, down, ch;
        int id, rotate, px, py; // extra data
    } DL[131072 + 256];
    int s[512], o[512], head, size;		
    void remove(int c) {
        DL[DL[c].right].left = DL[c].left;
        DL[DL[c].left].right = DL[c].right;
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].right; j != i; j = DL[j].right) {
                DL[DL[j].down].up = DL[j].up;
                DL[DL[j].up].down = DL[j].down;
                s[DL[j].ch]--;
            }
        }
    }
    void resume(int c) {
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].left; j != i; j = DL[j].left) {
                DL[DL[j].down].up = j;
                DL[DL[j].up].down = j;
                s[DL[j].ch]++;
            }
        }
        DL[DL[c].right].left = c;
        DL[DL[c].left].right = c;
    }
    int found;
    void print(int dep) {
        for (int i = 0; i < dep; i++) {
            int id = DL[o[i]].id, rt = DL[o[i]].rotate;
            int px = DL[o[i]].px, py = DL[o[i]].py;
            for (int p = 0; p < n; p++) {
                for (int q = 0; q < n; q++) {
                    if (pattern[id][rt][p][q] != ' ')
                        prob_out[0][px + p][py + q] = pattern[id][rt][p][q];
                }
            }
        }
        out_update();
    }
    void dfs(int dep) {
        if (found) return;
        if (DL[head].right == head) {
        	print(dep);
            found++;
            return;
        }
        int tmp = 0x3f3f3f3f, c, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right)
            if(s[i] < tmp)
                tmp = s[i], c = i;
        remove(c);
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[dep] = i;
            for(j = DL[i].right; j != i; j = DL[j].right)
                remove(DL[j].ch);
            dfs(dep+1);
            for(j = DL[i].left; j != i; j = DL[j].left)
                resume(DL[j].ch);
        }
        resume(c);
    }
    int getnode(int u, int d, int l, int r) {
        DL[size].up = u, DL[size].down = d;
        DL[size].left = l, DL[size].right = r;
        DL[u].down = DL[d].up = DL[l].right = DL[r].left = size;
        assert(size < 131072);
        return size++;
    }
    void newrow(int r[], int rn, int id, int rotate, int px, int py) {
        int i, j, h;
        for(i = 0; i < rn; i++) {
            DL[size].ch = r[i], s[r[i]]++;
            DL[size].id = id; // extra data
            DL[size].rotate = rotate; // extra data
            DL[size].px = px; // extra data
            DL[size].py = py; // extra data
            if(i) {
                j = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, DL[h].left, h);
            } else {
                h = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, size, size);
            }
        }
    }
    void init(int c) {// total column
        size = 0;
        head = getnode(0,0,0,0);
        int i;
        for(i = 1; i <= c; i++) {
            getnode(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} DLX;
int validPos(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n; 
}
char in[32767][128];
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        while (getchar() != '\n');
        DLX.init(n * n + m);
        
        int t = 0;
        while (gets(in[t]) && in[t][0] != '#') {
            t++;
        }
        memset(pattern, ' ', sizeof(pattern));
        
        int test = 0;
        for (int i = 0, idx = 0; i < m; i++) {
            int r = 0, c = 0;
            char label = -1;
            for (int j = 0; in[idx][j]; j++)
                if (in[idx][j] >= '0' && in[idx][j] <= '9')
                    label = in[idx][j];
                    
            for (r = 0; ; r++) {
                int ok = 0;
                for (int j = 0; in[idx][j]; j++)
                    if (in[idx][j] == label)
                        ok = 1;
                if (ok == 0)	break;
                for (int j = 0; in[idx][j]; j++) {
                    if (in[idx][j] == label) {
                        pattern[i][0][r][j] = in[idx][j];
                        c = max(c, j + 1);
                        test++;
                    }
                }
                idx++;
            }
            r = c = max(r, c);
            assert(r <= n && c <= n && r > 0);
            for (int rt = 1; rt < 4; rt++) {
                for (int p = 0; p < r; p++) {
                    for (int q = 0; q < c; q++) {
                        pattern[i][rt][p][q] = pattern[i][rt-1][q][r - 1 - p];
                    }
                }
            }
            for (int rt = 0; rt < 1; rt++) {
                for (int p = -20; p <= n; p++) { 
                    for (int q = -20; q <= n; q++) { // top-left corner
                        int ok = 1, row[512], rn = 0;
                        for (int p1 = 0; p1 < r && ok; p1++) {
                            for (int q1 = 0; q1 < c && ok; q1++) {
                                if (pattern[i][rt][p1][q1] != ' ') {
                                    ok &= validPos(p1 + p, q1 + q);
                                    row[rn++] = (p1 + p) * n + (q1 + q) + 1;
                                }
                            }
                        }
                        if (ok) {
                            row[rn++] = n * n + i + 1;
                            DLX.newrow(row, rn, i, rt, p, q);
                        }
                    }
                }	
            }
//			for (int kind = 0; kind < 4; kind++) {
//				for (int p = 0; p < r; p++, puts("")) {
//					for (int q = 0; q < c; q++)
//						printf("%c", pattern[i][kind][p][q]);
//				}
//				puts("---");
//			}
        }
        memset(mx, 0, sizeof(mx));
        DLX.found = 0;
        DLX.dfs(0);
        assert(DLX.found && test == n*n);
        if (DLX.found) {
            for (int i = 0; i < n; i++, puts("")) {
                for (int j = 0; j < n; j++) {
                    putchar(out[i][j]);
                    assert(out[i][j] != ' ');
                }
            }
        }
        puts("");
    }
    return 0;
}