计算机是蛋疼人类的好朋友系列(

实验室有个玩具,不知道是谁手欠买来的。是这样的一个东西:

据说它原来是个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

于是照着坐标,总算:

然后我就露出了满足的笑容。。。。。。。。。。