/*
2001/09 プロック・バイ・ブロックス
coded by Isaku WADA
 ┌───────────────────────────────┐
 │ Fig.1 のように,辺の長さが 1:2:3 の直方体のブロックがある。 │
 │このブロックを2個以上組み合わせて直方体(立方体も含む)を作ろ │
 │うと思うが,1つ条件がある。できあがった直方体が,(トウフを  │
 │包丁でスパッと切ったように)2つの直方体に分離できないように  │
 │したい。最低何個のブロックが必要だろうか。また,その個数での │
 │組み方は,回転・鏡像解を除いて何通りあるだろうか。なお,ブロ │
 │ックはすき間なく組み,直方体内部に空間があってはならない。  │
 │                               │
 │ たとえば Fig.2 は,矢印の間の太線で2つの直方体に分離でき  │
 │てしまうので,正解ではない。                 │
 └───────────────────────────────┘
 ┌───────────────────────────────┐
 │・プログラムの説明                      │
 │                               │
 │プログラムはブロック数を2から、解が得られるまで増やしてゆき │
 │ます。そして、「x*y*z」が「ブロック数*6」と等しく、x>=y>=zと │
 │なるような(x,y,z)すなわち直方体の寸法を求めてゆきます。    │
 │                               │
 │(x,y,z)が決まったら、周りに壁を作り(x+1)*(y+1)*(z+1)の1次元 │
 │配列を用意します。ブロックは6通りの置き方があり、1次元配列 │
 │に置けるように、あらかじめオフセット値でデータ化しておきます。│
 │                               │
 │探索は、再帰呼び出しをしながら、ブロックを1次元配列に置いて │
 │ゆきます。そして、決められたブロック数を、すき間なく置くこと │
 │ができたら、分離できないことを確かめ、さらに回転・鏡像を除い │
 │た後、記録して数えてゆきます。                │
 └───────────────────────────────┘
 ┌───────────────────────────────┐
 │・感想                            │
 │                               │
 │今回は難問でした。しかし、第112回「Fペントミノ」を参考に │
 │したところ、なんとか解くことができました。          │
 └───────────────────────────────┘
 Visual C++,Borland C++,LSI C,Turbo C,gcc で動作確認
*/

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

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum {
  MAX_BLOCK = 24,   /* 調べる最大のブロック数 */
  LOG_SIZE = 100,   /* 解を保存する個数 */
  SX=1, SY=2, SZ=3, /* ブロックの大きさ */
  SXYZ = SX*SY*SZ,
  MAX_CUBE = MAX_BLOCK*SXYZ
};

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int NumOfBlock; /* 現在のブロック数 */
int NumOfCube;  /* ブロック数×SXYZ */
int NumOfSol;   /* 得られた解の数 */
int LogStart;   /* 現在の(x,y,z)でのログの開始位置 */
int x,y,z;      /* 直方体の各軸の寸法 */
int Ofs[6][SXYZ];         /* 6通りの置き方のオフセット値 */
char Map[(MAX_CUBE+1)*4]; /* 壁を持った盤データ */
char Work[MAX_CUBE];      /* 壁を持たない盤データ */
char Temp[MAX_CUBE];      /* 回転する時に使う一時データ */
char*Log[LOG_SIZE];       /* 得られた解を保存する */

/*┌────────┐
 │直方体を表示する│
 └────────┘*/
void Print(char*a)
{
    int i,j,k;

    for (i=0;i<x;i++) {
        for (k=0;k<z;k++) {
            if (k) fputc(' ',stdout);
            for (j=0;j<y;j++) fputc(a[k+z*j+z*y*i],stdout);
        }
        fputc('\n',stdout);
    }
    fputc('\n',stdout);
}

/*┌──────────────────────────────┐
 │Work[] と Log[n] を比較してゆき、等しいものがあれば 1 を返す│
 └──────────────────────────────┘*/
int Same(void)
{
    int i,j,k,n,f; char*b;
    
    for (n=LogStart;n<NumOfSol;n++) {
        b=Log[n]; f=1;
        for (i=0;f&&i<NumOfBlock;i++) for (k=j=0;j<NumOfCube;j++)
         if (Work[j]=='A'+i) {
             if (k==0) k=b[j];
             else if (k!=b[j]) { f=0; break; }
         }
        if (f) return 1;
    }
    return 0;
}

/*┌──────────────┐
 │Work を X 軸について反転する│
 └──────────────┘*/
void TurnX(void)
{
    int i,j,k,p,q,r; char t;

    for (j=0;j<y;j++) for (k=0;k<z;k++)
     for (p=k+z*j,i=0;i<x/2;i++) {
         q=i*y*z+p; r=(x-i-1)*y*z+p;
         t=Work[q]; Work[q]=Work[r]; Work[r]=t;
     }
}

/*┌──────────────┐
 │Work を Y 軸について反転する│
 └──────────────┘*/
void TurnY(void)
{
    int i,j,k,p,q,r; char t;

    for (k=0;k<z;k++) for (i=0;i<x;i++)
     for (p=k+z*y*i,j=0;j<y/2;j++) {
         q=j*z+p; r=(y-j-1)*z+p;
         t=Work[q]; Work[q]=Work[r]; Work[r]=t;
     }
}

/*┌──────────────┐
 │Work を Z 軸について反転する│
 └──────────────┘*/
void TurnZ(void)
{
    int i,j,k,p; char t;

    for (i=0;i<x;i++) for (j=0;j<y;j++)
     for (p=z*j+z*y*i,k=0;k<z/2;k++)
     { t=Work[k+p]; Work[k+p]=Work[z-k-1+p]; Work[z-k-1+p]=t; }
}

/*┌────────────────────────────┐
 │グレイ符号に従って反転を行いながら、過去のログと比較する│
 └────────────────────────────┘*/
int CheckSame(void)
{
    if (Same()) return 1; TurnX();
    if (Same()) return 1; TurnY();
    if (Same()) return 1; TurnX();
    if (Same()) return 1; TurnZ();
    if (Same()) return 1; TurnX();
    if (Same()) return 1; TurnY();
    if (Same()) return 1; TurnX();
    if (Same()) return 1; TurnZ();
    return 0;
}

/*┌─────────────────────────┐
 │直方体 Work[] を2つの直方体に分離できれば1を返す│
 └─────────────────────────┘*/
int Separable(void)
{
    int i,j,k,f;

    for (i=1;i<x;i++) {
        for (f=j=0;j<y;j++) for (k=0;k<z;k++)
            if (Work[k+z*j+z*y*i]==Work[k+z*j+z*y*(i-1)]) f=1;
        if (f==0) return 1;
    }
    for (j=1;j<y;j++) {
        for (f=k=0;k<z;k++) for (i=0;i<x;i++)
            if (Work[k+z*j+z*y*i]==Work[k+z*(j-1)+z*y*i]) f=1;
        if (f==0) return 1;
    }
    for (k=1;k<z;k++) {
        for (f=i=0;i<x;i++) for (j=0;j<y;j++)
            if (Work[k+z*j+z*y*i]==Work[k-1+z*j+z*y*i]) f=1;
        if (f==0) return 1;
    }
    return 0;
}

/*┌────────────────────┐
 │x,y が等しい時、X 軸と Y 軸を入れ替える │
 └────────────────────┘*/
void SwapXY(void)
{
    int i,j,k;

    for (i=0;i<x;i++) for (j=0;j<y;j++) for (k=0;k<z;k++)
        Temp[k+z*y*j+z*i]=Work[k+z*j+z*y*i];
    for (i=0;i<NumOfCube;i++) Work[i]=Temp[i];
}

/*┌────────────────────┐
 │y,z が等しい時、Y 軸と Z 軸を入れ替える │
 └────────────────────┘*/
void SwapYZ(void)
{
    int i,j,k;

    for (i=0;i<x;i++) for (j=0;j<y;j++) for (k=0;k<z;k++)
        Temp[z*k+j+z*y*i]=Work[k+z*j+z*y*i];
    for (i=0;i<NumOfCube;i++) Work[i]=Temp[i];
}

/*┌────────────┐
 │直方体が完成した時の処理│
 └────────────┘*/
void CheckMain(void)
{
    int i,j,k,a=z+1,b=a*(y+1),p=0;

    for (i=0;i<x;i++) for (j=0;j<y;j++) for (k=0;k<z;k++)
        Work[p++]=Map[k+a*j+b*i];
    if (Separable()) return;
    if (CheckSame()) return;
    if (x==y) { SwapXY(); if (CheckSame()) return; }
    if (y==z) { SwapYZ(); if (CheckSame()) return; }
    if (x==z) { SwapXY(); if (CheckSame()) return; /* 立方体 */
                SwapYZ(); if (CheckSame()) return;
                SwapXY(); if (CheckSame()) return; }
    if (NumOfSol>=LOG_SIZE)
    { printf("LOG_SIZE が小さい\n"); exit(1); }
    Log[NumOfSol]=(char*)malloc(NumOfCube);
    if (Log[NumOfSol]==0)
    { printf("malloc() が0を返した\n"); exit(1); }
    for (i=0;i<NumOfCube;i++) Log[NumOfSol][i]=Work[i];
    Print(Work); NumOfSol++;
}

/*┌──────────────────────────┐
 │再帰呼び出しをしながら、Map[] にブロックを置いてゆく│
 └──────────────────────────┘*/
void Try(int pos,int level)
{
    int i,j;

    if (level==NumOfBlock) { CheckMain(); return; }
    while (Map[pos]) pos++;
    for (i=0;i<6;i++) {
        for (j=0;j<SXYZ;j++) if (Map[pos+Ofs[i][j]]) break;
        if (j!=SXYZ) continue;
        for (j=0;j<SXYZ;j++) Map[pos+Ofs[i][j]]=(char)('A'+level);
        Try(pos,level+1);
        for (j=0;j<SXYZ;j++) Map[pos+Ofs[i][j]]=0;
    }
}

/*┌───────────────────┐
 │データ構造の初期化と Try() の呼び出し │
 └───────────────────┘*/
void Sub(void)
{
    int i,j,k,p,a=z+1,b=a*(y+1);

    for (p=i=0;i<SX;i++) for (j=0;j<SY;j++) for (k=0;k<SZ;k++) {
        Ofs[0][p]=i+j*a+k*b; Ofs[1][p]=j+k*a+i*b;
        Ofs[2][p]=k+i*a+j*b; Ofs[3][p]=i+k*a+j*b;
        Ofs[4][p]=k+j*a+i*b; Ofs[5][p]=j+i*a+k*b; p++;
    }
    LogStart=NumOfSol;
    for (i=0;i<=x;i++) for (j=0;j<=y;j++) for (k=0;k<=z;k++) {
        p=i*b+j*a+k;
        if (i==x||j==y||k==z) Map[p]='@'; else Map[p]=0;
    }
    Try(0,0);
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock(); int nx;

    for (NumOfBlock=3;NumOfBlock<=MAX_BLOCK;NumOfBlock++) {
        NumOfCube=SXYZ*NumOfBlock;
        for (x=1;x<=NumOfCube;x++) 
         for (nx=NumOfCube/x,y=1;y<=x&&y<=nx;y++) {
             z=NumOfCube/(x*y);
             if (x*y*z==NumOfCube&&z<=y) Sub();
         }
        if (NumOfSol) {
            printf("ブロック数=%d  ",NumOfBlock);
            printf("同数解の数=%d  ",NumOfSol); break;
        }
    }
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}