cubemanuel.c

1995年ACM contest FINAL试题和源码

/*

1995-96 ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland
December 9, 1995


Problem: Cube

Idea:			Erwin Achermann, ETH Zurich
Implementation:	Manuel Bleichenbacher, Head Judge

Source file: cube.c / cube.p
Input file: cube.in
Output file: cube.out

*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>


typedef enum {
	FALSE = 0,
	TRUE = 1
} bool;


/* rotation */

const int cRotation1[27] =
	{  2,  5,  8,  1,  4,  7,  0,  3,  6,
	  11, 14, 17, 10, 13, 16,  9, 12, 15,
	  20, 23, 26, 19, 22, 25, 18, 21, 24 };
	  
const int cRotation2[27] =
	{ 18, 19, 20,  9, 10, 11,  0,  1,  2,
	  21, 22, 23, 12, 13, 14,  3,  4,  5,
	  24, 25, 26, 15, 16, 17,  6,  7,  8 };
	 
const int cRotation3[27] =
	{  2, 11, 20,  5, 14, 23,  8, 17, 26,
	   1, 10, 19,  4, 13, 22,  7, 16, 25,
	   0,  9, 18,  3, 12, 21,  6, 15, 24 };

/* translation */

const int cTranslation1[27] =
	{  1,  2, -1,  4,  5, -1,  7,  8, -1,
	  10, 11, -1, 13, 14, -1, 16, 17, -1,
	  19, 20, -1, 22, 23, -1, 25, 26, -1 };

const int cTranslation2[27] =
	{  9, 10, 11, 12, 13, 14, 15, 16, 17,
	  18, 19, 20, 21, 22, 23, 24, 25, 26,
	  -1, -1, -1, -1, -1, -1, -1, -1, -1 };

const int cTranslation3[27] =
	{  3,  4,  5,  6,  7,  8, -1, -1, -1,
	  12, 13, 14, 15, 16, 17, -1, -1, -1,
	  21, 22, 23, 24, 25, 26, -1, -1, -1 };


typedef char Cube[28];
const Cube cEmptyCube = "                           ";

const Cube cPiece[7] =
{
	"aaaa                       ",
	"bb b                       ",
	"ccc c                      ",
	"dd  dd                     ",
	"ee e     e                 ",
	"ff f        f              ",
	"gg g      g                "
};

typedef struct {
	int	nPieces;
	int	piece[1728];
} CPiecesList;

CPiecesList gCPieces[7];

FILE*	gFileOut;


bool TransformCube (Cube cube, int t1, int t2, int t3, int r1, int r2, int r3);
void GenerateCPieces();
void GenerateSolutions();
void PrintCube ( int pieceNo[] );


bool TransformCube (Cube cube, int t1, int t2, int t3, int r1, int r2, int r3)
{
	int i, j;
	Cube c;
	
	/* translation */
	for (i = 0; i < t1; i++) {
		strcpy(c, cEmptyCube);
		for (j = 0; j < 27; j++) {
			if (cTranslation1[j] == -1 && cube[j] != ' ')
				return FALSE;	/* a small cube would be moved out of the big cube */
			c[ cTranslation1[j] ] = cube[j];
		}
		strcpy(cube, c);
	}
	for (i = 0; i < t2; i++) {
		strcpy(c, cEmptyCube);
		for (j = 0; j < 27; j++) {
			if (cTranslation2[j] == -1 && cube[j] != ' ')
				return FALSE;	/* a small cube would be moved out of the big cube */
			c[ cTranslation2[j] ] = cube[j];
		}
		strcpy(cube, c);
	}
	for (i = 0; i < t3; i++) {
		strcpy(c, cEmptyCube);
		for (j = 0; j < 27; j++) {
			if (cTranslation3[j] == -1 && cube[j] != ' ')
				return FALSE;	/* a small cube would be moved out of the big cube */
			c[ cTranslation3[j] ] = cube[j];
		}
		strcpy(cube, c);
	}
	
	/* rotation */
	for (i = 0; i < r1; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation1[j] ] = cube[j];
		strcpy(cube, c);
	}
	for (i = 0; i < r2; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation2[j] ] = cube[j];
		strcpy(cube, c);
	}
	for (i = 0; i < r3; i++) {
		for (j = 0; j < 27; j++)
			c[ cRotation3[j] ] = cube[j];
		strcpy(cube, c);
	}
	return TRUE;
}


void GenerateCPieces()
{
	int i, j, k, c;
	int t1, t2, t3, r1, r2, r3;
	Cube cube;
	
	/* for all seven pieces do ... */
	for (i = 0; i < 7; i++) {
		gCPieces[i].nPieces = 0;
		for (t1 = 0; t1 < 3; t1++)
			for (t2 = 0; t2 < 3; t2++)
				for (t3 = 0; t3 < 3; t3++)
					for (r1 = 0; r1 < 4; r1++)
						for (r2 = 0; r2 < 4; r2++)
							for (r3 = 0; r3 < 4; r3++)
							
								/* no rotation for piece a */
								if (i > 0 || ( r1 + r2 + r3 == 0) ) {
									strcpy (cube, cPiece[i]);
									/* transform piece */
									if ( TransformCube (cube, t1, t2, t3, r1, r2, r3) ) {
										/* compress it */
										k = 1; c = 0;
										for (j = 0; j < 27; j++) {
											if (cube[j] != ' ')
												c |= k;
											k <<= 1;	/* shift one */
										}
										
										/* is compressed cube already there? */
										for (j = 0; j < gCPieces[i].nPieces; j++)
											if (gCPieces[i].piece[j] == c)
												break;
										if (j >= gCPieces[i].nPieces)
											gCPieces[i].piece[ gCPieces[i].nPieces++ ] = c;
									}
								}
	}
}


void GenerateSolutions( int pieceNo[], int n, int piece )
{
	int i;
	
	if (n < 7) {	/* try to add all possible pieces  */
		for (i = 0; i < gCPieces[n].nPieces; i++)
			if ( (piece & gCPieces[n].piece[i]) == 0 ) {	/* no collision */
				pieceNo[n] = i;
				GenerateSolutions( pieceNo, n+1,
							piece | gCPieces[n].piece[i] );
			}
	} else	/* we have a solution; print it */
		PrintCube( pieceNo );
}


void PrintCube( int pieceNo[] )
{
	int i, j, k;
	char buf[28];
	
	k = 1;
	for (i = 0; i < 27; i++) {
		for (j = 0; j < 7; j++)
			if (gCPieces[j].piece[pieceNo[j]] & k) {
				buf[i] = 'a' + j;
				break;
			}
		k <<= 1;
	}
	buf[27] = '\0';
	fprintf(gFileOut, "%s\n", buf);
}
		

int main(int argc, char* argv[])
{
	int pieceNo[7];
	
	gFileOut = fopen("cube.out", "w");
	assert( gFileOut != 0 );
	
	GenerateCPieces();
	GenerateSolutions(pieceNo, 0, 0);
	
	fclose( gFileOut );

	return 0;
}