/*
2000/10 ウサギと犬
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Figのような盤と十円玉3個,百円玉1個を使ってふたりで遊ぶ │
 │ゲームを紹介する。遊び方は以下の通り。          │
 │                             │
 │ @図のH,K,Jに十円玉を一個ずつ置き,猟犬とする     │
 │ A百円玉はウサギで,猟犬のいないところならどこに置いても│
 │  よい                         │
 │ B先手は猟犬                      │
 │ C線に沿って隣が空いていればその○に,猟犬のうちの一匹が│
 │  移動する。ただし、バックはできない(たとえば図のFから │
 │  B,C,D,E,Gには行けるが,H,I,Jには行けない)    │
 │ Dウサギも隣が空いていれば線に沿って移動する。方向は自由│
 │ E以下CとDを交互に続ける               │
 │                             │
 │ 最終的にウサギを動けなくしたら猟犬の勝ち,猟犬の包囲網を│
 │通り抜けたら(犬はバックができないのだからウサギが犬のうし │
 │ろに回り込めば)ウサギの勝ちである。なお,千日手(同じ場面の│
 │繰り返し)になった場合は猟犬側にその解消義務がある。    │
 │                             │
 │ さてこのゲーム,実は猟犬側に必勝法がある。猟犬をコンピュ│
 │ータが担当し,人と対戦する必勝プログラムを作ってほしい。対│
 │戦の表示方法はご自由にどうぞ。              │
 │                             │
 │      A                      │
 │     /│\                     │
 │    B─C─D                    │
 │    │\│/│                    │
 │    E─F─G                    │
 │    │/│\│                    │
 │    H─I─J                    │
 │     \│/                     │
 │      K                      │
 │  Fig.4 ウサギと犬                   │
 └─────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │ 基本は、複数の目的地を持つダイクストラ法(最短路問題)です。│
 │                              │
 │ パズルの状態として char Map[11] を持ちます。関数     │
 │MapToNum()はMapの識別番号を返します。逆に、関数NumToMap()は │
 │識別番号からMapへ展開します。状態と識別番号は1対1に対応し │
 │ます。状態の総数は Combination(11,4)×4=1320 だけあります。 │
 │                              │
 │ 配列 unsigned char DistTbl[1320] は、勝ち決定状態からの距 │
 │離(最小ターン数)を識別番号ごとに記録します。配列      │
 │int PrevTbl[1320]は、後で最短路をたどるために直前の識別番号 │
 │を記録します。                       │
 │                              │
 │ まずプログラムは、距離の配列を 255 で埋めます。次に、負け │
 │決定状態の距離を254にします。そして、全ての勝ち決定状態につ │
 │いて直前の状態の距離を0にし、対応するPrevTblに勝ち決定状態 │
 │の識別番号を記録します。                  │
 │                              │
 │ 続いてプログラムは、まだ距離が255の状態についてループしま │
 │す。そこから猟犬をどれか動かし、続いてウサギを動かします。新│
 │たに得られた状態の距離が 253 以下ならば、その値に1を足した │
 │値を新しい距離として記録します。同時に PrevTbl にその識別番 │
 │号を記録します。この時、猟犬の動かし方が複数ある場合は、最も│
 │距離が小さいものを選びます。また、ウサギの動かし方が複数ある│
 │場合は、最悪の距離を選びます。これをテーブルが変化しなくなる│
 │まで繰り返します。これで最短路がわかります。        │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │ 組合せと整数を対応させるための関数InitComb(),CombToNum(), │
 │NumToComb()は、作るのに苦労しましたが、汎用性があり速度もメ │
 │モリ使用効率も優れたものになりました。今回のパズル以外でも役│
 │立つと思います。                      │
 └──────────────────────────────┘
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.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

/*┌─────────────┐
 │エラー処理を含む malloc() │
 └─────────────┘*/
static void*DebugMalloc(size_t s) {
    void*p=malloc(s);
    if (p==0) { printf("malloc(%u)が0を返しました\n",s); exit(1); }
    return p;
}
#define malloc DebugMalloc

/*
 ┌───────────────────────────────┐
 │組合せの整数化                        │
 │                                   │
 │例えば、0 1 2 3 4の5種類(n=5,n>=0)の要素があるものとします。 │
 │この中から3つ要素(r=3,0<=r<=n)を取り出す場合を考えます。   │
 │取り出し方は10通りあって、辞書順での番号と組合せを列挙すると、│
 │ 0:(0,1,2) 1:(0,1,3) 2:(0,1,4) 3:(0,2,3) 4:(0,2,4)    │
 │ 5:(0,3,4) 6:(1,2,3) 7:(1,2,4) 8:(1,3,4) 9:(2,3,4)    │
 │となります。各関数の役割は以下のとおりです。         │
 │    ・unsigned int InitComb(int n,int r)           │
 │      内部テーブルを初期化し、組合せが何通りあるかを返します │
 │    ・unsigned int CombToNum(int*vec)             │
 │      与えられた組合せの辞書順での番号を返します       │
 │      (配列 vec[0..r-1] は、小さい順にソートされていること)  │
 │    ・void NumToComb(unsigned int num,int*vec)        │
 │      辞書順での番号から、組合せへ展開します         │
 └───────────────────────────────┘
*/
unsigned int**CombTbl[2]; /* 内部テーブル(2つの行列) */

unsigned int InitComb(int n,int r)
{
    unsigned int**a=CombTbl[0],**b=CombTbl[1]; int i,j,c=n-r+1;

    if (a) { for (i=0;a[i];i++) free(a[i]); free(a); CombTbl[0]=0; }
    if (b) { for (i=0;b[i];i++) free(b[i]); free(b); CombTbl[1]=0; }
    if (n<0||r<0||r>n) return 0;
    CombTbl[0]=a=(unsigned int**)malloc(sizeof*a*(r+1)); a[r]=0;
    CombTbl[1]=b=(unsigned int**)malloc(sizeof*b*(r+1)); b[r]=0;
    if (r==0) return 1;
    for (i=0;i<r;i++) a[i]=(unsigned int*)malloc(sizeof**a*c);
    for (i=0;i<r;i++) b[i]=(unsigned int*)malloc(sizeof**b*c);
    for (i=0;i<r;i++) a[i][c-1]=1;
    for (j=1;j<c;j++) a[r-1][j]=1;
    for (i=r-2;i>=0;i--) for (j=c-2;j>0;j--)
        a[i][j]=a[i][j+1]+a[i+1][j];
    for (i=0;i<r;i++) a[i][0]=0;
    for (i=0;i<r;i++) for (j=1;j<c;j++)
        b[i][j-1]=a[i][j]+=a[i][j-1];
    for (i=r-2;i>=0;i--) for (j=0;j<c-1;j++) b[i][j]+=b[i+1][j];
    if (c==1) for (i=0;i<r;i++) b[i][0]=1;
    else for (i=0;i<r;i++) b[i][c-1]=b[i][c-2]+1;
    for (i=0;i<r;i++) for (j=1;j<c;j++) if (b[i][j]<=b[i][j-1])
    { printf("InitComb(%d,%d)で桁があふれました\n",n,r); exit(1); }
    return b[0][c-1];
}

unsigned int CombToNum(int*vec)
{
    int i; unsigned int*p,num=0;

    for (i=0;(p=CombTbl[0][i])!=0;i++) num+=p[vec[i]-i];
    return num;
}

void NumToComb(unsigned int num,int*vec)
{
    int i,j=0; unsigned int*p;

    for (i=0;(p=CombTbl[1][i])!=0;i++) {
        while (p[j]<=num) j++;
        num-=CombTbl[0][i][j]; vec[i]=j+i;
    }
}

/*┌────────┐
 │定数・変数の宣言│
 └────────┘*/
enum { A,B,C,D,E,F,G,H,I,J,K,SIZE };
enum { NOTHING, DOG, RABBIT };
unsigned char*DistTbl;     /* 勝ち決定状態への距離(最小ターン数) */
int*PrevTbl;               /* 後で最短路をたどるための記録場所   */
char Map[SIZE],            /* パズルの状態                       */
 Level[]="01112223334",    /* 猟犬はレベルが高い所には行けません */
 Start[]="HJK",            /* 猟犬の初期位置                     */
 MoveTbl[][9]={/*A*/"BCD", /* ウサギが移動できる場所             */
   /*B*/"ACEF",/*C*/"ABDF",/*D*/"ACFG",/*E*/"BFH", /*F*/"BCDEGHIJ",
   /*G*/"DFJ", /*H*/"EFIK",/*I*/"FHJK",/*J*/"FGIK",/*K*/"HIJ"},
 Str[][3]={"A","B","C","D","E","F","G","H","I","J","K"};
#define MARK(X) (Map[X]==DOG?"★":Map[X]==RABBIT?"●":Str[X])

/*┌─────────────────────┐
 │Map を表示して、ウサギの位置を読み取ります│
 └─────────────────────┘*/
int Show(char*msg)
{
    static char buf[80]; int answer,s=SIZE;

#if defined(__CYGWIN__) || defined(UNIX)
    printf("\x1b[2J");
#else
    system("CLS");
#endif
    printf("\n  Cマガ電脳クラブ ウサギと犬\n\n");
    printf("\t     %s     \n",         MARK(A)         );
    printf("\t   /│\   \n"                          );
    printf("\t %s─%s─%s \n", MARK(B),MARK(C),MARK(D) );
    printf("\t │\│/│ \n"                          );
    printf("\t %s─%s─%s \n", MARK(E),MARK(F),MARK(G) );
    printf("\t │/│\│ \n"                          );
    printf("\t %s─%s─%s \n", MARK(H),MARK(I),MARK(J) );
    printf("\t   \│/   \n"                          );
    printf("\t     %s     \n",         MARK(K)         );
    printf("\n %s > ",msg);
    fgets(buf,sizeof buf,stdin); answer=buf[0];
    if (answer>='a'&&answer<='z') answer-='a'-'A';
    if (answer=='Z'||(s<='Q'-'A'&&answer=='Q')) exit(0);
    return answer-'A';
}

/*┌──────────┐
 │状態を整数へ変換する│
 └──────────┘*/
int MapToNum(char*Map)
{
    int i,j=0,p=0,vec[4];

    for (i=0;;i++) if (Map[i]) {
        if (Map[i]==RABBIT) p=j;
        vec[j++]=i;
        if (j==4) break;
    }
    return((int)CombToNum(vec)<<2)+p;
}

/*┌──────────┐
 │整数を状態へ変換する│
 └──────────┘*/
void NumToMap(char*Map,int num)
{
    int i,j=0,p=num&3,vec[4];

    NumToComb(num>>2,vec);
    for (i=0;i<SIZE;i++)
     if (j<4&&i==vec[j])
         if (j++==p) Map[i]=RABBIT; else Map[i]=DOG;
     else Map[i]=0;
}

/*┌───────────────────┐
 │負け決定状態の距離を 254 に設定します │
 └───────────────────┘*/
void SetLose(int NumSize)
{
    int num,rabbit,dog,LoseFlag;

    for (num=0;num<NumSize;num++) {
        /* 猟犬のレベルがウサギよりも小さければ、負け決定状態です */
        NumToMap(Map,num); LoseFlag=1;
        for (rabbit=0;Map[rabbit]!=RABBIT;rabbit++) ;
        for (dog=0;dog<SIZE;dog++) if (Map[dog]==DOG)
          if (Level[dog]>Level[rabbit]) LoseFlag=0;
        if (LoseFlag) DistTbl[num]=254;
    }
}

/*┌───────────────────────┐
 │勝ち決定状態の直前の状態の距離を0に設定します│
 └───────────────────────┘*/
void SetGoal(void)
{
    int rabbit,dog,NewDog,num,goal; char*p,*q;

    for (rabbit=0;rabbit<SIZE;rabbit++)
     if (strlen(MoveTbl[rabbit])==3) {
         /* 移動できる場所が3つしかないところにウサギを置き、
            周りを猟犬で囲めば、勝ち決定状態が得られます。*/
         memset(Map,0,SIZE); Map[rabbit]=RABBIT;
         for (p=MoveTbl[rabbit];*p;p++) Map[*p-'A']=DOG;
         goal=MapToNum(Map);
         for (p=MoveTbl[rabbit];*p;p++)
          for (q=MoveTbl[dog=*p-'A'];*q;q++)
           if (Level[NewDog=*q-'A']>=Level[dog]&&Map[NewDog]==0) {
               Map[NewDog]=DOG; Map[dog]=0; num=MapToNum(Map);
               PrevTbl[num]=goal; DistTbl[num]=0;
               Map[NewDog]=0; Map[dog]=DOG;
            }
     }
}

/*┌───────────────────────┐
 │num の状態から、勝ち決定状態へ移動できるなら、│
 └───────────────────────┘*/
/*┌───────────────────────┐
 │DistTbl[num] と PrevTbl[num] を更新します   │
 └───────────────────────┘*/
int Update(int num)
{
    int BestDog=0,BestNew=0,distance,Min=255,Max;
    int dog,rabbit,NewDog,NewRabbit; char*p,*q;

    NumToMap(Map,num);
    for (rabbit=0;Map[rabbit]!=RABBIT;rabbit++) ;
    for (dog=0;dog<SIZE;dog++) if (Map[dog]==DOG)
     for (p=MoveTbl[dog];*p;p++) 
      if (Level[NewDog=*p-'A']<=Level[dog]&&Map[NewDog]==0) {
          Max=0; Map[NewDog]=DOG; Map[dog]=0;
          for (q=MoveTbl[rabbit];*q;q++)
           if (Map[NewRabbit=*q-'A']==0) {
               Map[NewRabbit]=RABBIT; Map[rabbit]=0;
               distance=DistTbl[MapToNum(Map)];
               if (distance>Max) Max=distance;
               Map[rabbit]=RABBIT; Map[NewRabbit]=0;
           }
          if (Max<Min) { Min=Max; BestDog=dog; BestNew=NewDog; }
          Map[dog]=DOG; Map[NewDog]=0;
      }
    if (Min<=253) {
        DistTbl[num]=(unsigned char)(Min+1); Map[BestDog]=0;
        Map[BestNew]=DOG; PrevTbl[num]=MapToNum(Map); return 1;
    } else return 0;
}

/*┌────────┐
 │テーブルの初期化│
 └────────┘*/
void MakeTable(void)
{
    int num,change,NumSize=(int)InitComb(SIZE,4);

    if ((unsigned int)NumSize>(1<<(sizeof(int)*8-2))/sizeof*PrevTbl)
    { printf("問題が大きすぎます\n"); exit(1); } else NumSize<<=2;
    if (PrevTbl) free(PrevTbl);
    if (DistTbl) free(DistTbl);
    PrevTbl=(int*)malloc(sizeof*PrevTbl*NumSize);
    DistTbl=(unsigned char*)malloc(NumSize);
    memset(DistTbl,255,NumSize);
    SetLose(NumSize); SetGoal();
    do for (num=change=0;num<NumSize;num++)
        if (DistTbl[num]==255&&Update(num)) change=1;
    while (change);
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
void main(void)
{
    double StartTime=clock(); static char buf[80];
    int num,rabbit,NewRabbit,OkFlag; char*p;

    /* for (num=0;num<1000;num++) */ MakeTable();
    sprintf(buf,"テーブルの計算に約 %.3f 秒かかりました。\n\n"
      " ウサギの初期位置",(clock()-StartTime)/CLOCKS_PER_SEC);
    for (;;) {
        memset(Map,0,SIZE);
        for (p=Start;*p;p++) Map[*p-'A']=DOG;
        rabbit=Show(buf);
        while (rabbit<0||rabbit>=SIZE||Map[rabbit])
            rabbit=Show("エラー  ウサギの初期位置");
        Map[rabbit]=RABBIT;
        for (;;) {
            num=MapToNum(Map);
            if (DistTbl[num]>=254) { Show("猟犬の負け"); break; }
            Show("[ENTER]で継続"); NumToMap(Map,PrevTbl[num]);
            if (DistTbl[num]==0)   { Show("猟犬の勝ち"); break; }
            NewRabbit=Show("ウサギの移動先");
            for (;;) {
                OkFlag=0;
                if (NewRabbit>=0&&NewRabbit<SIZE&&Map[NewRabbit]==0)
                 for (p=MoveTbl[rabbit];*p;p++)
                  if (NewRabbit==*p-'A') OkFlag=1;
                if (OkFlag) break;
                NewRabbit=Show("エラー  ウサギの移動先");
            }
            Map[rabbit]=0; Map[NewRabbit]=RABBIT; rabbit=NewRabbit;
        }
        strcpy(buf,"ウサギの初期位置('Z'で終了)");
    }
}