The goal of this problem is to write a program which will take from 1 to 5
puzzle pieces such as
those shown below and arrange them, if possible, to form a square.
An example set of pieces is shown here.
The pieces cannot be rotated or flipped from their original orientation
in an attempt to form a
square from the set. All of the pieces must be used to form the
square. There may be more than
one possible solution for a set of pieces, and not every arrangement
will work even with a set for
which a solution can be found. Examples using the above set of
pieces are shown here.
The input file for this program contains several puzzles (i.e. sets of
puzzle pieces) to be solved.
The first line of the file is the number of pieces in the first puzzle.
Each piece is then specified by
listing a single line with two integers, the number of rows and
columns in the piece, followed by
one or more lines which specify the shape of the piece.
The shape specification consists of `0' and
`1' characters, with the `1' characters indicating the solid shape
of the puzzle (the `0' characters
are merely placeholders). For example, piece `A' above would be
specified as follows:
2 3
111
101
The pieces should be numbered by the order they are encountered in the
puzzle. That is, the first
piece in a puzzle is piece #1, the next is piece #2, etc. All pieces
may be assumed to be valid and no larger than 4 rows by 4 columns.
The line following the final line of the last piece contains the
number of pieces in the next puzzle,
again followed by the puzzle pieces and so on. The end of the input file
is indicated by a zero in place of the number of puzzle pieces.
Your program should report a solution, if one is possible, in the
format shown by the examples
below. A 4-row by 4-column square should be created, with each piece
occupying its location in
the solution. The solid portions of piece #1 should be replaced
with `1' characters, of piece #2
with `2' characters, etc. The solutions for each puzzle should be
separated by a single blank line.
If there are multiple solutions, any of them is acceptable.
For puzzles which have no possible solution simply
report ``No solution possible''.
4
2 3
111
101
4 2
01
01
11
01
2 1
1
1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1
0
1112
1412
3422
3442
No solution possible
1133
1153
2223
2444
試圖把代碼寫得更好看,但貌似失敗了。
#include <stdio.h>
#include <algorithm>
using namespace std;
struct DancingLinks {
int left, right, up, down, ch;
int rh; // 額外的 data
} DL[100000 + 1001];
int s[1001], o[1001], head, size;
int n; // this problem need n for output process.
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;
int data[1000][100];
void print(int k) {
int i, j;
int g[4][4];
int r[105], rn;
for(i = 0; i < k; i++) {
rn = 0;
for(j = 0; data[DL[o[i]].rh][j] > 0; j++)
r[rn++] = data[DL[o[i]].rh][j];
for(j = 1; j < rn; j++)
g[(r[j]-n-1)/4][(r[j]-n-1)%4] = r[0];
}
for(i = 0; i < 4; i++, puts(""))
for(j = 0; j < 4; j++)
printf("%d", g[i][j]);
}
void dfs(int dep) {
if(found) return;
if(DL[head].right == head) {
found = 1;
print(dep);
return;
}
int tmp = 0xffff, 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;
return size++;
}
void newrow(int r[], int rn, int rh) {
int i, j, h;
for(i = 0; i < rn; i++) {
DL[size].ch = r[i], s[r[i]]++;
DL[size].rh = rh; // 額外的 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;
}
}
int main() {
int i, j, k, x, y, a, b;
char g[20][20];
int first = 0;
while(scanf("%d", &n) == 1 && n) {
if(first) puts("");
first = 1;
int column = n+16, r[500], row = 0;
init(column);
for(i = 0; i < n; i++) {
scanf("%d %d", &x, &y);
for(j = 0; j < x; j++)
scanf("%s", g[j]);
for(j = 0; j+x <= 4; j++) {
for(k = 0; k+y <= 4; k++) {
int rn = 0;
r[rn++] = i+1;
for(a = 0; a < x; a++)
for(b = 0; b < y; b++)
if(g[a][b] == '1') {
r[rn++] = (j+a)*4 + k+b + n + 1;
}
newrow(r, rn, row);
for(a = 0; a < rn; a++)
data[row][a] = r[a];
data[row][rn] = -1;
row++;
}
}
}
found = 0;
dfs(0);
if(!found)
puts("No solution possible");
}
return 0;
}
文章定位: