实验室有个玩具，不知道是谁手欠买来的。是这样的一个东西：
据说它原来是个3x3x3的正方体，不知道又是谁手欠给展开了。
由于智商很宝贵的原因，我拿手里摆弄了好几天都没给它恢复成一个正方体。
怒，写个搜索算法。
#include <stdio.h>
#define sbyte signed char // sbyte: (-128 to +127)
#define SIZE 3 // Size of cube.
#define AREA (SIZE * SIZE) // Area of a face of cube.
#define VOLUME (SIZE * SIZE * SIZE) // Volume of cube.
void printblocks(sbyte* n)
// n: Blocks no. in (x, y, z) = (i / AREA, i / SIZE % SIZE, i % SIZE) where (0 <= i < VOLUME) => i = x * AREA + y * SIZE + z where (0 <= x, y, z < SIZE).
{
sbyte l[VOLUME]; // Location of each block.
sbyte i; // Loop variable.
// Write the location of each block.
for (i = 0; i < VOLUME; i++)
l[n[i]] = i;
// Print out the location table.
for (i = 0; i < VOLUME; i++)
printf("%d: (%d, %d, %d)\n",
i + 1,
l[i] / AREA + 1,
l[i] / SIZE % SIZE + 1,
l[i] % SIZE + 1);
printf("\n");
return;
}
sbyte calculateLocation(sbyte l, sbyte d)
// l: Location of current block.
// d: Direction of current block from. (+-)1 means x(+-), (+-)2 means y(+-), (+-)3 means z(+-).
{
sbyte c[3] = {l / AREA, l / SIZE % SIZE, l % SIZE}; // Coordinate of location.
sbyte s = d > 0 ? 1 : -1; // Calculate the sign of direction.
if(d < 0) d = -d; // Calculate the absolute value of direction.
c[d - 1] += s; // Calculate the target ocation
if(c[d - 1] >= SIZE || c[d - 1] < 0)
return -1; // Out of the cube.
else
return c[0] * AREA + c[1] * SIZE + c[2]; // Return the new location value.
}
void searchblock(sbyte* t, sbyte* n, sbyte d, sbyte l)
// t: Blocks type. 0 for straight, 1 for angled.
// n: Blocks no. in (x, y, z) = (i / AREA, i / SIZE % SIZE, i % SIZE) where (0 <= i < AREA) => i = x * AREA + y * SIZE + z where (0 <= x, y, z < SIZE).
// d: Direction of current block from. (+-)1 means x(+-), (+-)2 means y(+-), (+-)3 means z(+-).
// l: Location of current block.
{
sbyte cn = n[l]; // Current block no.
sbyte nl; // Location of next block.
sbyte i; // Loop variable.
if (cn == VOLUME - 1) { // All blocks are set.
printblocks(n);
return;
}
if (t[cn] == 0) { // Current block is straright.
nl = calculateLocation(l, d); // Calculate the location of next block.
if ( nl == -1 // Location is out of the cube.
|| n[nl] != -1) // Location is used.
return;
n[nl] = cn + 1;
searchblock(t, n, d, nl); // Search the possible location of next block.
n[nl] = -1;
} else {
for (i = -3; i <= 3; i++) { // Traversal of all directions.
if(i != d // Not currect direction
&& i != -d) { // Not the opposite disection
// Same as straight block, but direction differs.
nl = calculateLocation(l, i);
if ( nl == -1
|| n[nl] != -1)
continue;
n[nl] = cn + 1;
searchblock(t, n, i, nl);
n[nl] = -1;
}
}
}
return;
}
int main(void)
{
sbyte t[VOLUME]; // Block type. 0 for straight, 1 for angled.
sbyte n[VOLUME]; // Blocks no. in (x, y, z) = (i / AREA, i / SIZE % SIZE, i % SIZE) where (0 <= i < AREA) => i = x * AREA + y * SIZE + z where (0 <= x, y, z < SIZE).
sbyte i,x,y,z,d; // Loop variable.
t[0] = 0; // First block is straight, which means where the first block from, where it go.
t[VOLUME - 1] = -1; // Type of last block is not used.
for (i = 1; i <= VOLUME - 2; i++)
t[i] = (getchar() == '0') ? 0 : 1;
memset(n, -1, sizeof(n));
for (x = 0; x < (SIZE + 1) / 2; x++)
for (y = x; y < (SIZE + 1) / 2; y++)
for (z = y; z < (SIZE + 1) / 2; z++)
{
i = x * AREA + y * SIZE + z;
n[i] = 0;
if(x + 1 <= y)
searchblock(t, n, 1, i);
if(x <= y + 1 && y + 1 <= z)
searchblock(t, n, 2, i);
if(y <= z + 1)
searchblock(t, n, 3, i);
n[i] = -1;
}
printf("END\n");
return 0;
}
运行输入输出如下
0...0..0...0.0....0.0.0.0
1: (1, 1, 1)
2: (1, 1, 2)
3: (1, 1, 3)
4: (2, 1, 3)
5: (2, 1, 2)
6: (2, 2, 2)
7: (2, 3, 2)
8: (3, 3, 2)
9: (3, 2, 2)
10: (3, 1, 2)
11: (3, 1, 3)
12: (3, 2, 3)
13: (2, 2, 3)
14: (1, 2, 3)
15: (1, 2, 2)
16: (1, 2, 1)
17: (2, 2, 1)
18: (2, 1, 1)
19: (3, 1, 1)
20: (3, 2, 1)
21: (3, 3, 1)
22: (2, 3, 1)
23: (1, 3, 1)
24: (1, 3, 2)
25: (1, 3, 3)
26: (2, 3, 3)
27: (3, 3, 3)
1: (1, 1, 1)
2: (1, 1, 2)
3: (1, 1, 3)
4: (1, 2, 3)
5: (1, 2, 2)
6: (2, 2, 2)
7: (3, 2, 2)
8: (3, 3, 2)
9: (2, 3, 2)
10: (1, 3, 2)
11: (1, 3, 3)
12: (2, 3, 3)
13: (2, 2, 3)
14: (2, 1, 3)
15: (2, 1, 2)
16: (2, 1, 1)
17: (2, 2, 1)
18: (1, 2, 1)
19: (1, 3, 1)
20: (2, 3, 1)
21: (3, 3, 1)
22: (3, 2, 1)
23: (3, 1, 1)
24: (3, 1, 2)
25: (3, 1, 3)
26: (3, 2, 3)
27: (3, 3, 3)
END
于是照着坐标，总算：
然后我就露出了满足的笑容。。。。。。。。。。