/*
2004/6 切手切って乗りきって
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.1のように、5×5の切手シートがある。これをFig.2の│
 │ように4×4と3×3の2つに組み直したい。シートはミシン目│
 │に沿って切り離す。25枚に切り離したらやさしすぎるので、「│
 │4枚」に切り離して組み直して4×4と3×3を作っていただき│
 │たい。もちろん、図を見てわかるように、できあがった4×4と│
 │3×3に、切手の図柄が逆さや横向きになっているものがあって│
 │はいけない。このときの5×5のシートの切り離し方は何通りあ│
 │るだろうか。                       │
 │ なお、切り離しのパターンが、回転したり鏡像になっているも│
 │のは、別の解とはしない。                 │
 │                             │
 │  Fig.1 5×5の切手シート              │
 │  ┌─┬─┬─┬─┬─┐                │
 │  │C│C│C│C│C│                │
 │  ├─┼─┼─┼─┼─┤                │
 │  │C│C│C│C│C│                │
 │  ├─┼─┼─┼─┼─┤                │
 │  │C│C│C│C│C│                │
 │  ├─┼─┼─┼─┼─┤                │
 │  │C│C│C│C│C│                │
 │  ├─┼─┼─┼─┼─┤                │
 │  │C│C│C│C│C│                │
 │  └─┴─┴─┴─┴─┘                │
 │                             │
 │  Fig.2 4×4、3×3に組み直す           │
 │                             │
 │  (a)4×4     (b)3×3          │
 │  ┌─┬─┬─┬─┐  ┌─┬─┬─┐         │
 │  │C│C│C│C│  │C│C│C│         │
 │  ├─┼─┼─┼─┤  ├─┼─┼─┤         │
 │  │C│C│C│C│  │C│C│C│         │
 │  ├─┼─┼─┼─┤  ├─┼─┼─┤         │
 │  │C│C│C│C│  │C│C│C│         │
 │  ├─┼─┼─┼─┤  └─┴─┴─┘         │
 │  │C│C│C│C│                  │
 │  └─┴─┴─┴─┘                  │
 └─────────────────────────────┘
 ┌──────────────┬────┬───────┐
 │コンパイラ         │実行時間│ファイルサイズ│
 ├──────────────┼────┼───────┤
 │Microsoft Visual C++ 6.0  │0.390 秒│ 36864 byte │
 │Microsoft Visual C++ 2003  │0.406 秒│ 49152 byte │
 │Borland C++ 5.5.1 for Win32 │0.562 秒│ 55808 byte │
 │gcc-2.953(djgpp)      │0.440 秒│ 111765 byte │
 │gcc-2.953(cygwin)      │0.485 秒│ 23530 byte │
 │LSI C-86 Ver 3.30 試食版  │1.160 秒│ 15558 byte │
 │Turbo C Ver 1.5(small model)│0.990 秒│ 13232 byte │
 ├──────────────┼────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP   │
 └──────────────┴────────────┘
┌───────────────────────────────┐
│解答:6通り                         │
│┌┬───┐┌───┐┌┬┬┐ ┌┬───┐┌───┐┌──┐│
│││   ││   │││││ ││   ││   ││  ││
│├┤┌┐ ││┌┐ ││└┘│ ├┴─┐ │├┬┐ ││  ││
││││├┐│││└┐│└──┘ │  ├┐│││└┐│└──┘│
││└┘│└┤└┴─┴┘     │  │└┤└┴─┴┘    │
│└──┴─┘          └──┴─┘         │
│                               │
│┌┬───┐┌───┐┌──┐ ┌┬───┐┌───┐┌┬─┐│
│││   ││   ││ ┌┤ ││   ││   │││ ││
│├┴─┐ │├─┐ ││ ││ │└─┐ │├─┐ ││└─┤│
││ ┌┴┐││ └┐│└─┴┘ ├─┬┴┐││ └┐│└──┘│
││ │ └┤└──┴┘     │ │ └┤└──┴┘    │
│└─┴──┘          └─┴──┘         │
│                               │
│┌┬───┐┌───┐┌──┐ ┌┬───┐┌───┐┌──┐│
││└┐  │├┐  ││  │ │└┐  │├┐  ││  ││
││ ├──┤│└┬─┤│  │ ├─┴┬┐││└┬┐││  ││
│├─┤  ││ │ │└──┘ │  │└┤│ │└┤└──┘│
││ │  │└─┴─┘     │  │ │└─┴─┘    │
│└─┴──┘          └──┴─┘         │
└───────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum { UP,DOWN,LEFT,RIGHT };      /* 切り離すミシン目を伸ばす方向 */
enum { VERTICAL,LEFT_HOR,RIGHT_HOR }; /* 切り離し方 */
enum { PRINT_DRAW, PRINT_FLUSH }; /* Print() 関数の動作を決める */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
char Map[11][11]=         /* 5×5のシートを分離するための配列 */
{{1,1,1,1,1,1,1,1,1,1,1}, /* 添え字が共に偶数ならミシン目の交差点 */
 {1,0,0,0,0,0,0,0,0,0,1}, /* 片方が奇数ならミシン目の辺 */
 {1,0,0,0,0,0,0,0,0,0,1}, /* 共に奇数なら切手の中心 */
 {1,0,0,0,0,0,0,0,0,0,1},
 {1,0,0,0,0,0,0,0,0,0,1}, /* 交差点が1か2なら線に含まれている */
 {1,0,0,0,0,0,0,0,0,0,1}, /* 特に2の場合は垂直分離線である */
 {1,0,0,0,0,0,0,0,0,0,1},
 {1,0,0,0,0,0,0,0,0,0,1}, /* 辺が1の場合は分離線に含まれている */
 {1,0,0,0,0,0,0,0,0,0,1},
 {1,0,0,0,0,0,0,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1,1}};

char Map33[5][5];   /* 3×3のシート */
char Map44[5][5];   /* 4×4のシート */
char Map55[5][5];   /* 5×5のシート */
char Comp[5][5];    /* 回転と鏡像を格納する */
char Log[10][5][5]; /* 解の保管場所 */
int  NumOfSol;      /* 解の数 */

/*┌────────────────────────┐
 │mapのピース情報を罫線情報へ変換してkeiへ書き込む│
 └────────────────────────┘*/
void MapToKei(char kei[6][13],char map[5][5])
{
    int x,y,c;
    static char s[]=" │││─┘┐┤─└┌├─┴┬┼",temp[7][7];

    memset(temp,0,sizeof temp);
    for (y=0;y<5;y++) for (x=0;x<5;x++) temp[y+1][x+1]=map[y][x];
    for (y=0;y<6;y++) {
        kei[y][0]=0;
        for (x=0;x<6;x++) {
            c=0;
            if (temp[y][x]  !=temp[y][x+1]  ) c|=1<<UP;
            if (temp[y][x]  !=temp[y+1][x]  ) c|=1<<LEFT;
            if (temp[y][x+1]!=temp[y+1][x+1]) c|=1<<RIGHT;
            if (temp[y+1][x]!=temp[y+1][x+1]) c|=1<<DOWN;
            sprintf(kei[y]+strlen(kei[y]),"%.2s",s+c*2);
        }
    }
}

/*┌────┐
 │解の表示│
 └────┘*/
void Print(int mode)
{
    int y; static char buf[6][80],k5[6][13],k4[6][13],k3[6][13];

    if (mode==PRINT_DRAW) {
        MapToKei(k5,Map55); MapToKei(k4,Map44); MapToKei(k3,Map33);
        if (strlen(buf[0])) for (y=0;y<6;y++) strcat(buf[y]," ");
        for (y=0;y<6;y++) {
            sprintf(buf[y]+strlen(buf[y]),"%.12s",k5[y]);
            sprintf(buf[y]+strlen(buf[y]),"%.10s",k4[y]);
            sprintf(buf[y]+strlen(buf[y]),"%.8s", k3[y]);
        }
    }
    if ((mode==PRINT_FLUSH&&buf[0][0])||strlen(buf[0])>40) {
        for (y=0;y<6;y++) { printf("%s\n",buf[y]); buf[y][0]=0; }
        printf("\n");
    }
}

/*┌──────────────────────┐
 │Comp を右回りに回転させて過去の解と比較する │
 └──────────────────────┘*/
int Rot(void)
{
    int i,j; static char Temp[5][5],Tbl[]={0,2,4,1,3};

    memcpy(Temp,Comp,sizeof Comp);
    for (i=0;i<5;i++) for (j=0;j<5;j++)
        Comp[j][4-i]=Tbl[(int)Temp[i][j]];
    for (i=0;i<NumOfSol;i++)
        if (memcmp(Comp,Log[i],sizeof Comp)==0)
            return 1;
    return 0;
}

/*┌───────────────────────┐
 │Comp を左右対称に反転させて過去の解と比較する │
 └───────────────────────┘*/
int Rev(void)
{
    int i,j; static char Temp[5][5],Tbl[]={0,2,1,4,3};

    memcpy(Temp,Comp,sizeof Comp);
    for (i=0;i<5;i++) for (j=0;j<5;j++)
        Comp[i][4-j]=Tbl[(int)Temp[i][j]];
    for (i=0;i<NumOfSol;i++)
        if (memcmp(Comp,Log[i],sizeof Comp)==0)
            return 1;
    return 0;
}

/*┌──────────────────┐
 │(x,y)と連続している場所をcodeにする │
 └──────────────────┘*/
void SetMap55(int x,int y,int code)
{
    int cx,cy;

    if (Map55[y][x]) return;
    Map55[y][x]=(char)code; cx=x*2+1; cy=y*2+1;
    if (Map[cy][cx-1]==0) SetMap55(x-1,y,code);
    if (Map[cy-1][cx]==0) SetMap55(x,y-1,code);
    if (Map[cy][cx+1]==0) SetMap55(x+1,y,code);
    if (Map[cy+1][cx]==0) SetMap55(x,y+1,code);
}

/*┌──────────────────┐
 │n×nのmapのcodeの固まりを削除する。 │
 └──────────────────┘*/
void Remove(char map[5][5],int n,int code)
{
    int i,j;

    for (i=0;i<n;i++) for (j=0;j<n;j++)
        if (map[i][j]==code) map[i][j]=0;
}

/*┌─────────────────────┐
 │Map55のcodeの固まりをn×nのmapへ詰め込む。│
 │成功したら個数を返す。失敗したら0を返す。│
 └─────────────────────┘*/
int Pack(char map[5][5],int n,int code)
{
    int i,j=0,x,y,u,v,s,t=0,count=0;

    for (s=0;s<n;s++) {
        for (t=0;t<n;t++) if (map[s][t]==0) break;
        if (t<n) break;
    }
    for (i=0;i<5;i++) {
        for (j=0;j<5;j++) if (Map55[i][j]==code) break;
        if (j<5) break;
    }
    for (y=0;y<5;y++) for (x=0;x<5;x++)
     if (Map55[y][x]==code) {
         u=x-j+t; v=y-i+s;
         if (u<0||u>=n||v>=n||map[v][u])
         { Remove(map,n,code); return 0; }
         map[v][u]=(char)code; count++;
    }
    return count;
}

/*┌───────────────────────┐
 │4×4と3×3のシートに組みなおせたら1を返す│
 └───────────────────────┘*/
int Ok(void)
{
    int a,b,c,d,  p,q;

    memset(Map55,0,sizeof Map55);
    memset(Map33,0,sizeof Map33);
    memset(Map44,0,sizeof Map44);
    SetMap55(0,0,1); SetMap55(4,0,2);
    SetMap55(0,4,3); SetMap55(4,4,4);
    for (a=1;a<=4;a++) {
        p=Pack(Map33,3,a);
        if (p==0) continue;
        for (b=1;b<=4;b++) if (b!=a) {
            if (p==9) {
                if (Pack(Map44,4,b)==0) continue;
            }else {
                q=Pack(Map33,3,b);
                if (q==0) continue;
                if (p+q!=9) { Remove(Map33,3,b); continue; }
            }
            for (c=1;c<=4;c++) if (c!=a&&c!=b) {
                if (Pack(Map44,4,c)==0) continue;
                for (d=1;d<=4;d++) if (d!=a&&d!=b&&d!=c)
                     if (Pack(Map44,4,d)) return 1;
                Remove(Map44,4,c);
            }
            if (p==9) Remove(Map44,4,b);
        }
        Remove(Map33,3,a);
    }
   return 0;
}

/*┌────────────────────────┐
 │回転と鏡像をチェックし、新しければLogに記録する │
 └────────────────────────┘*/
void Check(void)
{
    memcpy(Comp,Map55,sizeof Map55);
    if (NumOfSol&&(Rot()||Rot()||Rot()
         ||Rev()||Rot()||Rot()||Rot())) return;
    Print(PRINT_DRAW);
    if (NumOfSol>=sizeof Log/sizeof Log[0])
    { printf("Log size too small\n"); exit(EXIT_FAILURE); }
    memcpy(Log[NumOfSol++],Map55,sizeof Map55);
}

/*┌───────────────┐
 │5×5のシートを4枚に切り離す│
 └───────────────┘*/
void Separate(int phase,int x,int y,int dir)
{
    static int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
    int sx=x+dx[dir],sy=y+dy[dir],i;
    int tx=sx+dx[dir],ty=sy+dy[dir];

    Map[sy][sx]=1;
    if (phase==VERTICAL&&ty==10)
        for (i=2;i<10;i+=2) Separate(LEFT_HOR,0,i,RIGHT);
    else if (phase==LEFT_HOR&&Map[ty][tx]==2)
        for (i=2;i<10;i+=2) Separate(RIGHT_HOR,10,i,LEFT);
    else if (phase==RIGHT_HOR&&Map[ty][tx]==2) {
        if (Ok()) Check(); /* 分離が完成したので処理をする */
    }else if (Map[ty][tx]==0) {
        if (phase==VERTICAL) Map[ty][tx]=2; else Map[ty][tx]=1;
        for (i=UP;i<=RIGHT;i++) if ((i^1)!=dir) /* バック以外 */
            Separate(phase,tx,ty,i);
        Map[ty][tx]=0;
    }
    Map[sy][sx]=0;
}

/*┌────────────────────┐
 │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(void)
{
    double StartTime=clock();

    Separate(VERTICAL,2,0,DOWN); /* 1列目の上から下に向かって分離 */
    Separate(VERTICAL,4,0,DOWN); /* 2列目の上から下に向かって分離 */
    Print(PRINT_FLUSH); printf("%3d 通り。   ",NumOfSol);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}