/*
2004/10 ロード・オブ・ザ・リンク
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.1のように、8×8の格子の交点に10個の円が描かれ、│
 │A〜Eのアルファベットが2つずつ書き込まれている。このAと│
 │A、BとB、CとC、DとD、EとEを「リンク線」でつなぎた│
 │い。リンク線は格子の線に沿って進み、1つの交点には1本のリ│
 │ンク線しか通れない。つまり、5本のリンク線はお互いに(自分│
 │自身でも)交わらない、ということである。もちろん、アルファ│
 │ベットの書いてある円は1本のリンク線しかつなげない。リンク│
 │線が通らない交点があってもかまわないし、リンク線の長さが最│
 │短である必要もない。何通りのつなぎ方があるか。すべてのつな│
 │ぎ方を示してほしい。                   │
 │ たとえばFig.2の例で、AとA、BとB、CとCをつなぐ3本│
 │のリンク線を描くと、Fig.3のように4通りの解がある。   │
 │                             │
 │Fig.1 8×8の格子と10個の円             │
 │                             │
 │・・・A・・・・                     │
 │・B・・・・C・                     │
 │・・・・・・・・                     │
 │・C・・・・・E                     │
 │・・・D・・・・                     │
 │E・・・・・B・                     │
 │・・A・・・・・                     │
 │・・・・・・・D                     │
 │                             │
 │Fig.2 4×4の格子と6個の円の例            │
 │                             │
 │A・・・                         │
 │・・BA                         │
 │CB・C                         │
 │・・・・                         │
 │                             │
 │Fig.3 4通りの解                    │
 │                             │
 │A━━┓ A━━┓                    │
 │・┏BA ・┏BA                    │
 │CB┏C CB・C                    │
 │┗━┛・ ┗━━┛                    │
 │                             │
 │A━━┓ A┏━┓                    │
 │・・BA ┗┛BA                    │
 │CB┛C CB┛C                    │
 │┗━━┛ ┗━━┛                    │
 └─────────────────────────────┘
 ┌────────┐
 │解答:1通り  │
 │┏━━A┏━━┓│
 │┃B━━┛┏C┃│
 │┃┏━━━┛┏┛│
 │┃C┏━━┓┃E│
 │┗┓┃D┓┃┃┃│
 │E┃┗┓┃┃B┃│
 │┃┗A┃┃┗━┛│
 │┗━━┛┗━━D│
 └────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 元の盤の情報から作業用の盤Map[19][19]を作成することから │
 │始まります。Mapの添え字が共に偶数なら格子点です。また、周 │
 │りを壁で囲みます。添え字の片方が奇数なら線となります。  │
 │ 探索は、後で説明する枝刈りの効率を上げるために、EABC│
 │Dの順にリンク線をつなげてゆきます。順は各アルファベット間│
 │の距離が長い順に並び替えることによって自動的に求めます。こ│
 │こでの距離とは厳密には横方向の差と縦方向の差の大きいほうで│
 │す。                           │
 │ 始めに、Eの片方の点から線を再帰呼び出しを使って伸ばして│
 │ゆきます。残りのEに到達したら、次はA、そして、BCDの順│
 │に伸ばしてゆきます。DのリンクをつなぐことができたらMapを │
 │表示します。                       │
 │ 一つのリンク線が完成したら、残りのリンク線をつなぐことが│
 │可能かどうかで枝刈りをします。例えばEのリンク線が完成した│
 │ら、Aの片方から、もう片方のAへリンク線をつなぐことができ│
 │るかどうかを確認します。Eのリンク線によってAのリンク線が│
 │つなぐことができなければ、その時のEのリンク線を捨てて、次│
 │のEのリンク線に移ります。これをBCDのアルファベットでも│
 │行います。ABCDのリンクが、求めたEのリンク線で切断され│
 │ていなければ、次にAのリンク線を再帰呼び出しで伸ばしてゆき│
 │、完成したら、同様にBCDのリンクを切断していないかどうか│
 │で枝刈りをします。                    │
 │ この方法で枝刈りをする場合、最初はEのように、距離が離れ│
 │ているものから行うのが効率的です。なぜなら、リンクを完成さ│
 │せた時に、他のリンク線を切断する可能性が大きいからです。 │
 │ リンクの切断を避ける枝刈りの効果で、約5倍速くなり、順序│
 │を工夫した効果により、さらに約2倍速くなりました。    │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 枝刈りの時に、他のリンクが切断されたかどうかを判定するの│
 │に意外と時間がかかり、劇的に高速にはなりませんでした。たぶ│
 │ん、もっと上手な方法があると思いますが、思いつきませんでし│
 │た。紙と鉛筆で解いた時にはリンクが切断されたかどうかは、一│
 │目瞭然で、簡単に解を見つけることができたのですが。    │
 └─────────────────────────────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Visual Studio C++ 6.0     │  7.906 秒│ 49512 byte │
 │Visual Studio C++ 2003     │  8.296 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │ 12.828 秒│ 54272 byte │
 │gcc-2.953(djgpp)      │ 13.626 秒│ 108763 byte │
 │gcc-2.953(cygwin)      │ 13.500 秒│ 20215 byte │
 │LSI C-86 Ver 3.30 試食版  │ 24.550 秒│ 14568 byte │
 │Turbo C Ver 1.5(small model)│ 22.520 秒│ 11982 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴─────────────┘
*/

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

/*┌──────┐
 │マクロの宣言│
 └──────┘*/
#define BYTE     unsigned char
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
#define ABS(X)   ((X)>=0?(X):-(X))

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum { CX=8, CY=8 };         /* 盤の大きさ */
enum { EMPTY,A,B,C,D,E,Z };  /* Map[][]のとる値 */
enum { UP,DOWN,LEFT,RIGHT }; /* 方向を表す */

/*┌─────┐
 │変数の宣言│
 └─────┘*/
BYTE Points[CY][CX]= /* 盤とアルファベットの配置 */
{{0,0,0,A,0,0,0,0},
 {0,B,0,0,0,0,C,0},
 {0,0,0,0,0,0,0,0},
 {0,C,0,0,0,0,0,E},
 {0,0,0,D,0,0,0,0},
 {E,0,0,0,0,0,B,0},
 {0,0,A,0,0,0,0,0},
 {0,0,0,0,0,0,0,D}};

BYTE Distance[Z-1];        /* アルファベット間の距離 */
BYTE Order[Z-1];           /* 処理するアルファベットの順番 */
BYTE PosX[2][Z];           /* アルファベットの横位置 */
BYTE PosY[2][Z];           /* アルファベットの縦位置 */
BYTE Map[CY*2+3][CX*2+3];  /* 作業用の盤 */
int  NumOfSol;             /* 見つかった解の数 */
BYTE Flag[Z*2]={1};        /* 枝刈り用。リンクが通れるMapなら1 */
BYTE Area[CY*2+3][CX*2+3]; /* 枝刈り用。リンクが通れる場所なら1 */

/*┌────────────────┐
 │keyの大きい順に配列を並び替える │
 └────────────────┘*/
void RevSort(BYTE*key,BYTE*data,int n)
{
    int i,j; BYTE k,d;

    for (i=n-1;i>0;i--)
     if (key[i-1]<key[i]) {
         k=key[i-1]; d=data[i-1]; j=i;
         do { key[j-1]=key[j]; data[j-1]=data[j]; j++; }
         while (j<n&&k<key[j]);
         key[j-1]=k; data[j-1]=d;
     }
}

/*┌────────────┐
 │Map[][] の状態を表示する│
 └────────────┘*/
void Print(void)
{
    int x,y,m;

    for (y=2;y<CY*2+1;y+=2) {
        for (x=2;x<CX*2+1;x+=2) {
            m=Map[y][x];
            if (m>Z) m-=Z;
            if (m!=Z)
                printf("%.2s"," ABCDEFGHIJKLMN"+m*2);
            else {
                if      (Map[y-1][x]&&Map[y+1][x]) printf("┃");
                else if (Map[y][x-1]&&Map[y][x+1]) printf("━");
                else if (Map[y][x-1]&&Map[y+1][x]) printf("┓");
                else if (Map[y][x+1]&&Map[y+1][x]) printf("┏");
                else if (Map[y][x-1]&&Map[y-1][x]) printf("┛");
                else if (Map[y][x+1]&&Map[y-1][x]) printf("┗");
                else                               printf("■");
            }
        }
        printf("\n");
    }
    printf("\n"); NumOfSol++;
}

/*┌───────────────────────┐
 │枝刈り用。(x,y)と連続しているArea[][]を1にする│
 └───────────────────────┘*/
void SetArea(int x,int y)
{
    if (Area[y][x]) return;
    Area[y][x]=1;
    if (Flag[Map[y][x-2]]) SetArea(x-2,y);
    if (Flag[Map[y-2][x]]) SetArea(x,y-2);
    if (Flag[Map[y][x+2]]) SetArea(x+2,y);
    if (Flag[Map[y+2][x]]) SetArea(x,y+2);
}

/*┌──────┐
 │解を探索する│
 └──────┘*/
void Search(int level,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,k;
    int tx=sx+dx[dir],ty=sy+dy[dir];

    Map[sy][sx]=Z;
    if (Map[ty][tx]==Order[level]) { /* リンクが繋がった */
        if (level==Z-2) Print(); /* 完成 */
        else {

            /* 枝刈りルーチン */
            /* 残りのリンクを切断しているかどうか調べる */
            for (i=level+1;i<Z-1;i++) {
                memset(Area,0,sizeof Area);
                k=Order[i]; Flag[k]=1;
                SetArea(PosX[0][k],PosY[0][k]);
                Flag[k]=0;
                if (Area[PosY[1][k]][PosX[1][k]]==0) {
                    /* リンクが切れたので抜ける */
                    Map[sy][sx]=0; return;
                }
            }
            /* 枝刈りルーチンの終わり */

            /* 次のリンクの開始 */
            k=Order[level+1];
            ty=PosY[0][k]; tx=PosX[0][k];
            Map[ty][tx]+=Z; /* スタート地点へ戻らないようにする */
            for (i=UP;i<=RIGHT;i++) Search(level+1,tx,ty,i);
            Map[ty][tx]-=Z;
        }
    }else if (Map[ty][tx]==0) {

        /* リンクを伸ばす */
        Map[ty][tx]=Z;
        for (i=UP;i<=RIGHT;i++) if ((i^1)!=dir) /* バック以外 */
            Search(level,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)
{
    int x,y,i,k; static BYTE c[Z]; double StartTime=clock();

    /* Map[][] と PosX[][] と PosY[][] の設定 */
    for (y=0;y<CY*2+3;y+=2) Map[y][0]=Map[y][CX*2+2]=Z; /*壁を作る*/
    for (x=0;x<CX*2+3;x+=2) Map[0][x]=Map[CY*2+2][x]=Z;
    for (y=0;y<CY;y++) for (x=0;x<CX;x++) {
        i=Points[y][x]; Map[y*2+2][x*2+2]=(BYTE)i;
        if (i) {
            PosX[c[i]][i]=(BYTE)(x*2+2);
            PosY[c[i]][i]=(BYTE)(y*2+2); c[i]++;
        }
    }

    /* アルファベット間の距離を求める */
    for (i=A;i<Z;i++) {
        Order[i-1]=(BYTE)i;
        x=PosX[0][i]-PosX[1][i]; y=PosY[0][i]-PosY[1][i];
        x=ABS(x); y=ABS(y); Distance[i-1]=(BYTE)MAX(x,y);
    }

    /* 離れているアルファベットほど先に処理をする */
    RevSort(Distance,Order,Z-1);

    /* 探索の開始 */
    k=Order[0]; x=PosX[0][k]; y=PosY[0][k];
    Map[y][x]+=Z; /* スタート地点へ戻らないようにする */
    for (i=UP;i<=RIGHT;i++) Search(0,x,y,i);

    printf("%5d 通りの解がありました  ",NumOfSol);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}