cuberolf.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:	Rolf Strebel, ETH Zurich

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

*/

#include <stdio.h>
#include <stdlib.h>

#define NOFP 7
#define MAXV 1000

typedef struct CubeDesc {
  int d[3];
  int a[27];
} CubeDesc, *Cube;

#define c_i(c,i,j,k) ((*(c)).a[(i)+3*(j)+9*(k)])
#define c_d(c,i)     ((*(c)).d[i])

CubeDesc part[NOFP] = {
  {{3,2,1},{1,1,1,1}},
  {{2,2,1},{1,1,0,1}},
  {{3,2,1},{1,1,1,0,1}},
  {{3,2,1},{1,1,0,0,1,1}},
  {{2,2,2},{1,1,0,1,0,0,0,0,0,1}},
  {{2,2,2},{1,1,0,0,1,0,0,0,0,1}},
  {{2,2,2},{1,0,0,1,1,0,0,0,0,1}},
};

FILE *fout;

/*--------------------------------*/
/* function prototypes */

void l_init(void);
int l_insert(int, int);
void error (char *str);
void c_print (Cube c);
CubeDesc shift (Cube c, int x, int y, int z);
CubeDesc rotate (Cube c, int x, int y, int z);
int code (Cube c);
void t_print (int p);
void init (void) ;
void gen (void);
void traverse (int p, int c);

/*--------------------------------*/
/* list section */

static struct {
  int v[MAXV];
  int nof;
} list[NOFP];

#define l_nof(p) (list[p].nof)
#define l_c(p,j) (list[p].v[j])

void l_init (void)
{
  int i;

  for (i = 0; i < NOFP; i++) {
    l_nof(i) = 0;
  }
}

int l_insert (int i, int c)
{
  int j;

  for (j = 0; j < l_nof(i); j++) {
    if (c == l_c(i,j)) return (0);
  }
  j = l_nof(i);
  l_c(i,j) = c;
  l_nof(i) = j + 1;
  return (1);
}

/*--------------------------------*/
/* error handling */

void error (char *str)
{
  fprintf (stderr, "--> ERROR: %s\n", str);
  exit (1);
}

/*--------------------------------*/
/* cube motion, print */

void c_print (Cube c)
{
  int j,k,l;

  for (j = 0; j < 3; j++) {
    for (k = 0; k < 3; k++) {
      for (l = 0; l < 3; l++) {
       fprintf (fout,"%c", (char)(c_i(c,j,k,l)?('O'):('.')));
      }
    }
  }
}

CubeDesc shift (Cube c, int x, int y, int z)
{
  CubeDesc d = {{0},{0}};
  int j,k,l;

  for (j = x; j < 3; j++) {
    for (k = y; k < 3; k++) {
      for (l = z; l < 3; l++) {
       c_i(&d,j,k,l) = c_i(c,j-x,k-y,l-z);
      }
    }
  }
  return (d);
}

CubeDesc rotate (Cube c, int x, int y, int z)
{
  CubeDesc d, e;
  int i,j,k,l;

  d = (*c);
  for (i = 0; i < x; i++) {
    for (j = 0; j < 3; j++) {
      for (k = 0; k < 3; k++) {
       for (l = 0; l < 3; l++) {
         c_i(&e,j,k,l) = c_i(&d,j,l,2-k);
       }
      }
    }
    d = e;
  }
  for (i = 0; i < y; i++) {
    for (j = 0; j < 3; j++) {
      for (k = 0; k < 3; k++) {
       for (l = 0; l < 3; l++) {
         c_i(&e,j,k,l) = c_i(&d,2-l,k,j);
       }
      }
    }
    d = e;
  }
  for (i = 0; i < z; i++) {
    for (j = 0; j < 3; j++) {
      for (k = 0; k < 3; k++) {
       for (l = 0; l < 3; l++) {
         c_i(&e,j,k,l) = c_i(&d,k,2-j,l);
       }
      }
    }
    d = e;
  }
  return (d);
}

/*--------------------------------*/
/* code (Cube --> int) */

int code (Cube c)
{
  int i;
  int j,k,l;
  
  i = 0;
  for (j = 0; j < 3; j++) {
    for (k = 0; k < 3; k++) {
      for (l = 0; l < 3; l++) {
       i = (i << 1) | c_i(c,j,k,l);
      }
    }
  }
  return (i);
}

/*--------------------------------*/
/* generation and traversal */

static int t_count;
static int t_tab[NOFP];
static char t_char[] = "abcdefg";

void t_print (int p)
{
  int i, j;
  char ch;

  for (i = 0; i < 27; i++) {
    ch = '.';
    for (j = 0; j < p; j++) {
      if (l_c(j,t_tab[j]) & (1 << i)) {
       ch = t_char[j]; 
       break;
      }
    }
    fprintf (fout,"%c", (char)ch);
  }
  fprintf (fout,"\n");
}
       
void init (void) 
{
  l_init ();
  t_count = 0;
}

void gen (void)
{
  int p;
  int j,k,l;
  int z;
  CubeDesc c, d, e;

  for (p = 0; p < NOFP; p++) {
    c = part[p];
    for (j = 0; j <= 3 - c_d(&c,0); j++) {
      for (k = 0; k <= 3 - c_d(&c,1); k++) {
       for (l = 0; l <= 3 - c_d(&c,2); l++) {
         d = shift (&c, j, k, l);
         if (p == 0) {
           l_insert (p, code(&d));
         } else {
           for (z = 0; z < 4; z++) {
             e = rotate (&d, 0, 0, z); l_insert (p, code(&e));
             e = rotate (&d, 1, 0, z); l_insert (p, code(&e));
             e = rotate (&d, 2, 0, z); l_insert (p, code(&e));
             e = rotate (&d, 3, 0, z); l_insert (p, code(&e));
             e = rotate (&d, 0, 1, z); l_insert (p, code(&e));
             e = rotate (&d, 0, 3, z); l_insert (p, code(&e));
           }
         }
       }
      }
    }
  }
}

void traverse (int p, int c)
{
  int i;
  int d;

  if (p == NOFP) {
    t_count++;
    t_print(p);
  } else {
    for (i = 0; i < l_nof(p); i++) {
      d = l_c(p,i);
      if (!(d & c)) {
       t_tab[p] = i;
       traverse (p+1, d | c);
      }
    }
  }
}

/*--------------------------------*/
/* main program */

#if DEBUG
void codeprint (int c)
{
  int i;

  for (i = 0; i < 27; i++) {
    printf ("%c",(char)(c&1)?('O'):('.'));
    c >>= 1;
  }
  printf ("\n");
}
#endif

int main (int argc, char **argv)
{
  if (argc > 1) error ("USAGE: cube");
  if (sizeof(int) < 4) error ("sizeof(int) too small");
  
  fout = fopen("cube.out", "w");
  init ();
  gen ();
#if DEBUG
  {
    int p, i;
  
    for (p = 0; p < NOFP; p++) {
      printf ("%i: nof= %i\n", (int)p, (int)l_nof(p));
    }
    p = 1;
    for (i = 0; i < l_nof(p); i++) {
      codeprint (l_c(p,i));
    }
  }
  exit (0);
#endif
  traverse (0, 0);
#if DEBUG
  printf ("%i\n", (int)t_count);
#endif
	fclose(fout);
	return 0;
}