/*
2002/03 Iトロミノ
coded by Isaku WADA
 ┌────────────────────────────┐
 │ Fig.1のように,正方形を3つ一列につないだ1×3の形状│
 │の板をIトロミノという。これを32枚使って,8×12の長│
 │方形にぴったり詰める。ただし,タタミ同様,十字型の継ぎ目│
 │(Fig.2)ができないようにしたい(もちろん,T字型はOK)。│
 │何通りの詰め方があるだろうか。なお,全体を回転したものや│
 │鏡像のものは別の解とはしない。             │
 │                 (出題:Donald E. Knuth)│
 │                            │
 │ Fig.1 Iトロミノ   Fig.2 十字型の継ぎ目    │
 │                            │
 │  ┌─┬─┬─┐     ┌──┬──┐       │
 │  │     │     ├┬─┴┬─┴┐      │
 │  └─┴─┴─┘     │├──╋┬┬┘      │
 │              │├──┤││       │
 │              ├┴─┬┤││       │
 │              └──┘└┴┘       │
 │                            │
 └────────────────────────────┘

 ┌────────────────────────────┐
 │解答:2通り                      │
 │                            │
 │No.1            No.2            │
 │┌┬──┬┬┬──┬──┐ ┌┬┬──┬┬──┬──┐ │
 ││├──┤│├┬─┴┬┬┤ ││├──┤├┬─┴┬┬┤ │
 ││├──┤││├──┤││ ││├──┤│├──┤││ │
 │├┴─┬┴┴┤├──┤││ ├┴┴┬─┴┤├──┤││ │
 │├┬─┴┬┬┴┴┬┬┴┴┤ ├┬─┴┬┬┴┴┬┬┴┴┤ │
 ││├──┤├──┤├┬┬┤ │├──┤├──┤├┬┬┤ │
 ││├──┤├──┤││││ │├──┤├──┤││││ │
 │├┴─┬┴┴┬─┴┤│││ ├┴─┬┴┴┬─┴┤│││ │
 │└──┴──┴──┴┴┴┘ └──┴──┴──┴┴┴┘ │
 │                            │
 └────────────────────────────┘

 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00197 秒│ 36864 byte │
 │Borland C++ 5.5 for Win32  │0.00263 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.00208 秒│ 111113 byte │
 │gcc-2.953(cygwin)      │0.00264 秒│ 374538 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00241 秒│ 14108 byte │
 │Turbo C Ver 1.5(small model)│0.00258 秒│ 11582 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium!!! 550 MHz │   OS:Windows 98   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │長方形を、壁に囲まれた大きさ(12+2)×(8+2)の一次元配列で表し │
 │ます。配列の値が0ならば空白で、-1なら壁です。プログラムは、 │
 │一番若い位置の空白にIトロミノを再帰呼び出しをしながら置いて│
 │ゆきます。一枚目なら配列に1を設定し、32枚目なら32を設定しま │
 │す。横のIトロミノなら、配列の相対位置+0,+1,+2に、縦のIトロ│
 │ミノなら配列の相対位置+0,+14,+28に設定してゆきます。この時、│
 │十字型の継ぎ目ができたら無視して次に進みます。       │
 │                              │
 │32枚置くことができたら、配列を罫線形式に変換して、回転や鏡像│
 │が過去にあったかどうか調べます。新しい配置ならば罫線形式を利│
 │用して表示します。罫線形式では、9×13個の継ぎ目の候補につい │
 │て罫線が上向きに伸びていれば第1ビットが立ち、同様に下なら第│
 │2、左なら第3、右なら第4ビットが立ちます。例えば継ぎ目がT│
 │字型ならば、下右左に罫線が伸びているので、第2、第3、第4ビ│
 │ットが立ち、結果2+4+8=14となります。            │
 │                              │
 │プログラムの一般性を高めるために、板(Iトロミノ)の長さと、長│
 │方形の大きさを任意に指定できるようにしました。また、長方形が│
 │正方形の場合は90度、270度回転の排除も行うようにしました。  │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │Iトロミノを長さ2に変更して、色々な長方形について試したとこ│
 │ろ、意外に敷き詰め方の組み合わせが少ないのに驚きました。タタ│
 │ミの敷き詰め方の自由度は小さいのですね。          │
 └──────────────────────────────┘
*/

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

/*┌────────────────────────┐
 │板の長さと、長方形の大きさと、Log の大きさの指定│
 └────────────────────────┘*/
#define L      3  /* デフォルト  3 */
#define SX    12  /* デフォルト 12 */
#define SY     8  /* デフォルト  8 */
#define LOG 1000

/*┌───────────────┐
 │Map で使う罫線の状態を表す定数│
 └───────────────┘*/
#define UP    1
#define DOWN  2
#define LEFT  4
#define RIGHT 8
#define ALL   (UP|DOWN|LEFT|RIGHT)

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Box[(SY+2)*(SX+2)];   /* 長方形の埋まり具合(含壁) */
char Buf[SY][SX];          /* Box の状態を一時的に記録 */
char Map[SY+1][SX+1];      /* 長方形内の罫線形式での状態 */
char OrgMap[SY+1][SX+1];   /* Map の初期状態 */
char Log[LOG][SY+1][SX+1]; /* 過去の記録 */
int  Count;                /* 解の数 */

/*┌───────────┐
 │現在の Map を出力する │
 └───────────┘*/
void Print(char map[][SX+1])
{
    int x,y; static char s[]=" │││─┘┐┤─└┌├─┴┬┼";
    static char b[SY+1][81],c;

    if (map==0&&c) {
        for (c=y=0;y<=SY;y++) { printf("%s\n",b[y]); b[y][0]=0; }
        return;
    }
    for (y=0;y<=SY;y++) for (x=0;x<=SX;x++)
        sprintf(b[y]+strlen(b[y]),"%.2s",s+map[y][x]*2);
    if (++c==79/((SX+1)*2))
        for (c=y=0;y<=SY;y++) { printf("%s\n",b[y]); b[y][0]=0; }
}

/*┌───────────────────┐
 │長方形の埋まり具合を罫線形式へ変換する│
 └───────────────────┘*/
void BufToMap(void)
{
    int x,y;

    memcpy(Map,OrgMap,sizeof Map);
    for (y=0;y<SY;y++) for (x=1;x<SX;x++)
     if (Buf[y][x-1]==Buf[y][x])
     { Map[y][x]&=LEFT|RIGHT|UP; Map[y+1][x]&=LEFT|RIGHT|DOWN; }
    for (x=0;x<SX;x++) for (y=1;y<SY;y++)
     if (Buf[y-1][x]==Buf[y][x])
     { Map[y][x]&=UP|DOWN|LEFT; Map[y][x+1]&=UP|DOWN|RIGHT; }
}

/*┌───────────────────┐
 │ログに Map と同じものがあれば 1 を返す│
 └───────────────────┘*/
int SameMap(void)
{
    int t;

    BufToMap();
    for (t=0;t<Count;t++)
     if (memcmp(Map,Log[t],sizeof Map)==0) return 1;
    return 0;
}

/*┌──────────┐
 │Buf を左右反対にする│
 └──────────┘*/
int LeftRight(void)
{
    int x,y; char temp[SY][SX];

    memcpy(temp,Buf,sizeof Buf);
    for (y=0;y<SY;y++) for (x=0;x<SX;x++)
     Buf[y][SX-1-x]=temp[y][x];
    return SameMap();
}

/*┌──────────┐
 │Buf を上下反対にする│
 └──────────┘*/
int UpDown(void)
{
    int x,y; char temp[SY][SX];

    memcpy(temp,Buf,sizeof Buf);
    for (y=0;y<SY;y++) for (x=0;x<SX;x++)
     Buf[SY-1-y][x]=temp[y][x];
    return SameMap();
}

/*┌──────────┐
 │Buf の軸を入れ替える│
 └──────────┘*/
int SwapRot(void)
{
    int x,y; char temp[SY][SX];

    memcpy(temp,Buf,sizeof Buf);
    for (y=0;y<SY;y++) for (x=0;x<SX;x++)
     Buf[x][y]=temp[y][x];
    return SameMap();
}

/*┌──────────────┐
 │ピタリと詰め終わった後の処理│
 └──────────────┘*/
void CheckMain(void)
{
    int x,y;

    for (y=0;y<SY;y++) for (x=0;x<SX;x++)
        Buf[y][x]=Box[(y+1)*(SX+2)+x+1];

    /* 回転と鏡像の排除 */
    if (SameMap()||LeftRight()||UpDown()||LeftRight()) return;
#if SX == SY
    if (SwapRot()||LeftRight()||UpDown()||LeftRight()) return;
#endif
    if (Count==LOG) { printf("LOG SIZE ERROR\n"); exit(1); }
    memcpy(Log[Count++],Map,sizeof Map);
}

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

    /* 詰め終わった時の処理 */
    if (level>SY*SX/L) { CheckMain(); return; }

    /* 壁や既に詰めた場所を飛ばす */
    while (Box[p]) p++;

    /* 水平に置けるか */
    for (i=0;i<L;i++) if (Box[p+i]) break;
    if (i==L&&(Box[p-SX-3]==Box[p-SX-2]||Box[p-SX-3]==Box[p-1])) {
        for (i=0;i<L;i++) Box[p+i]=(char)level;
        level++; Try(p); level--; /* 再帰呼び出し */
        for (i=0;i<L;i++) Box[p+i]=0;
    }

    /* 垂直に置けるか */
    for (i=0;i<L*(SX+2);i+=SX+2) if (Box[p+i]) break;
    if (i==L*(SX+2)&&(Box[p-SX-3]==Box[p-SX-2]
                    ||Box[p-SX-3]==Box[p-1])) {
        for (i=0;i<L*(SX+2);i+=SX+2) Box[p+i]=(char)level;
        level++; Try(p); level--; /* 再帰呼び出し */
        for (i=0;i<L*(SX+2);i+=SX+2) Box[p+i]=0;
    }
}

/*┌───────────────────┐
 │データ構造の初期化と Try() の呼び出し │
 └───────────────────┘*/
void Solve(void)
{
    int x,y;

#if SX * SY % L != 0
    printf("割り切れません\n"); exit(1);
#endif
    memset(OrgMap,ALL,sizeof OrgMap);

    for (y=0;y<=SY;y++) /* 外側の縦のデッパリを落とす */
    { OrgMap[y][0]&=UP|DOWN|RIGHT; OrgMap[y][SX]&=UP|DOWN|LEFT; }

    for (x=0;x<=SX;x++) /* 外側の横のデッパリを落とす */
    { OrgMap[0][x]&=LEFT|RIGHT|DOWN; OrgMap[SY][x]&=LEFT|RIGHT|UP; }

    memset(Box,0,sizeof Box);

    for (y=0;y<SY+2;y++) /* 縦の壁を作る */
    { Box[y*(SX+2)]=Box[y*(SX+2)+SX+1]=-1; }

    for (x=0;x<SX+2;x++) /* 横の壁を作る */
    { Box[x]=Box[(SY+1)*(SX+2)+x]=-1; }

    Count=0; Try(SX+2+1);
}

/*┌────────────────────┐
 │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

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve();
    for (i=0;i<Count;i++) Print(Log[i]);
    Print(0); printf("解の数 %d   ",Count);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}