/*
2003/10 どろけい
coded by Isaku WADA
 ┌──────────────────────────────┐
 │ Fig.1で,10円玉はどろぼう,100円玉は刑事である。どち│
 │らも線に沿って1つだけサークル(円)からサークルへ移動できる。│
 │刑事が先手であとは交互に動き,「動かない」というのは許されな│
 │い。バックもできる。刑事はどろぼうを捕まえたいが,当然どろぼ│
 │うはできるだけ逃げようとする。               │
 │ 刑事のあなたは,何手目でどろぼうを取り押さえることができる│
 │か。その最短手数と,そのときの手順を示していただきたい。  │
 │                              │
 │Fig.1「どろけい」の初期配置                │
 │                              │
 │     ○                        │
 │    /│\                       │
 │   ○ 百 十                      │
 │    \/\/                       │
 │    ○─○                       │
 │                              │
 └──────────────────────────────┘
 ┌──────────────────────────┐
 │解答:                       │
 │                          │
 │ 最短手数4手                   │
 │                          │
 │   ○     ○     泥     泥    │
 │  /│\   /│\   /│\   /│\   │
 │ ○ 刑 泥 ○ ○ 泥 ○ ○ ○ ○ ○ ○  │
 │  \/\/  \/\/  \/\/  \/\/   │
 │  ○─○   刑─○   刑─○   ○─刑   │
 │                          │
 │   ○     ○     泥     刑    │
 │  /│\   /│\   /│\   /│\   │
 │ 泥 ○ ○ 泥 刑 ○ ○ 刑 ○ ○ ○ ○  │
 │  \/\/  \/\/  \/\/  \/\/   │
 │  ○─刑   ○─○   ○─○   ○─○   │
 │                          │
 └──────────────────────────┘
 ┌──────────────┬───────┬───────┐
 │コンパイラ         │ 実行時間   │ファイルサイズ│
 ├──────────────┼───────┼───────┤
 │Microsoft Visual C++ 6.0  │0.000003125 秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.000002968 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.000004813 秒│ 54784 byte │
 │gcc-2.953(djgpp)      │0.000003407 秒│ 109883 byte │
 │gcc-2.953(cygwin)      │0.000003515 秒│ 20907 byte │
 │LSI C-86 Ver 3.30 試食版  │0.000009450 秒│ 14258 byte │
 │Turbo C Ver 1.5(small model)│0.000009950 秒│ 11878 byte │
 ├──────────────┼───────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP      │
 └──────────────┴───────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 状態は刑事とどろぼうの位置の6×6の組み合わせで表すこと│
 │ができます。状態を表す変数として、刑事のターンで後何手で捕│
 │まえられるかを表す KeijiStep[6][6]と、どろぼうのターンで後│
 │何手で捕まえられるかを表す ThiefStep[6][6]を用意しました。│
 │ 初期化としてThiefStep[0][0],ThiefStep[1][1]...ThiefStep │
 │[5][5]を0にします。これは、刑事がどろぼうを捕まえた状態だ│
 │からです。残りのThiefStepとKeijiStepの全てを無限を意味する│
 │127にしておきます。                    │
 │ プログラムは、捕まえた状態から初期状態へ向かって、時間を│
 │逆向きに進んで、刑事とどろぼうを交互に動かしてゆきます。そ│
 │して、初期状態のKeijiStepが無限でなくなった時に探索を終わ │
 │り手順を書き出します。                  │
 │ 刑事の動かし方を説明します。まず、KeijiStepが無限の配置 │
 │について考えます。そして、その状態から刑事を動かした全ての│
 │状態についてのThiefStepを調べます。刑事は最短で捕まえたい │
 │ので、その中で最も小さい値を選び、その値に1を足したものを│
 │KeijiStepに設定します。このとき、動きをNextKeijiに記録しま│
 │す。                           │
 │ どろぼうの動かし方を説明します。まず、ThiefStepが無限の │
 │配置について考えます。そして、その状態からどろぼうを動かし│
 │た全ての状態についてのKeijiStepを調べます。どろぼうは捕ま │
 │りたくないので、その中に無限があったら逃げます。KeijiStep │
 │の全てが無限でなかった場合、その中で最も大きな値を選び、そ│
 │の値に1を足したものをThiefStepに設定します。このとき、動 │
 │きをNextThiefに記録します。                │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 問題が単純で実行時間が短い割に、複雑で大きなプログラムに│
 │なってしまいました。                   │
 └─────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐  0
 │定数の宣言│ /│\
 └─────┘1 2 3
         \/\/
         4─5 */
#define N           6        /* サークルの総数 */
#define START_KEIJI 2        /* 刑事の初期位置 */
#define START_THIEF 3        /* 泥棒の初期位置 */
char*Lines[N]=               /* サークルとサークルを結ぶ線の情報 */
{"123","04","045","05","125","234"};
char*Str[]={"○","刑","泥"}; /* 解の表示で使う */
#define WIN   0              /* 泥棒を捕まえた配置を表す */
#define INF 127              /* 手数として十分大きな数(無限大) */
#define COL   4              /* 解の表示の時に横に並べる数 */

/*┌─────────────────────┐
 │変数の宣言(刑事と泥棒の配置を添え字にとる)│
 └─────────────────────┘*/
char KeijiStep[N][N]; /* 刑事のターンでの捕まえた時点からの手数 */
char ThiefStep[N][N]; /* 泥棒のターンでの捕まえた時点からの手数 */
char NextKeiji[N][N]; /* 捕まえるまでの刑事の足取り */
char NextThief[N][N]; /* 捕まえるまでの泥棒の足取り */

/*┌──────────────────────────┐
 │状態を書き出す。flushを1にすると、バッファを書き出す│
 └──────────────────────────┘*/
#define Z(X) Str[keiji==(X)?1:thief==(X)?2:0]
void PrintSub(int keiji,int thief,int flush)
{
    static char buf[5][80]; static int col; int i;

    if (flush==0) {
        if (col++) for (i=0;i<5;i++) strcat(buf[i]," ");
        i=(int)strlen(buf[0]);
        sprintf(buf[0]+i,"  %s  ",      Z(0)      );
        sprintf(buf[1]+i," /│\ "                 );
        sprintf(buf[2]+i,"%s %s %s", Z(1),Z(2),Z(3) );
        sprintf(buf[3]+i," \/\/ "                 );
        sprintf(buf[4]+i," %s─%s ",   Z(4),Z(5)    );
    }
    if ((flush&&col)||col==COL) {
        for (i=0;i<5;i++) { printf("%s\n",buf[i]); buf[i][0]=0; }
        printf("\n"); col=0;
    }
}

/*┌───────┐
 │結果を書き出す│
 └───────┘*/
void Print(void)
{
    int keiji=START_KEIJI,thief=START_THIEF,step=0;

    for (;;) {
        PrintSub(keiji,thief,0);
        keiji=NextKeiji[keiji][thief];
        PrintSub(keiji,thief,0); step++;
        if (ThiefStep[keiji][thief]==WIN) break;
        thief=NextThief[keiji][thief];
    }
    PrintSub(0,0,1); printf("最短手数 %d 手  ",step);
}

/*┌────────────────┐
 │ThiefStepとKeijiStepを初期化する│
 └────────────────┘*/
void Initialize(void)
{
    int keiji,thief;

    for (keiji=0;keiji<N;keiji++)
     for (thief=0;thief<N;thief++) {
        if (keiji==thief) ThiefStep[keiji][thief]=WIN; 
        else              ThiefStep[keiji][thief]=INF;
        KeijiStep[keiji][thief]=INF;
     }
}

/*┌──────────────────┐
 │最も短い手数になるように刑事を動かす│
 │解が見つかったら0を返す      │
 └──────────────────┘*/
int MoveKeiji(void)
{
    int keiji,thief,next,flag=0,step,Min,MinNext=0; char*ptr;

    for (keiji=0;keiji<N;keiji++) for (thief=0;thief<N;thief++)
     if (KeijiStep[keiji][thief]==INF) {
         Min=INF;
         for (ptr=Lines[keiji];*ptr;ptr++) {
             next=*ptr-'0'; step=ThiefStep[next][thief];
             if (step<Min) { Min=step; MinNext=next; }
         }
         if (Min<INF) {
             KeijiStep[keiji][thief]=(char)(Min+1);
             NextKeiji[keiji][thief]=(char)MinNext; flag=1;
         }
     }
    if (flag==0)
    { printf("パズルは解けませんでした\n"); exit(EXIT_FAILURE); }
    return KeijiStep[START_KEIJI][START_THIEF]==INF;
}

/*┌──────────────────┐
 │最も長い手数になるように泥棒を逃がす│
 └──────────────────┘*/
void MoveThief(void)
{
    int keiji,thief,next,step,Max,MaxNext=0; char*ptr;

    for (keiji=0;keiji<N;keiji++) for (thief=0;thief<N;thief++)
     if (ThiefStep[keiji][thief]==INF) {
         Max=WIN;
         for (ptr=Lines[thief];*ptr;ptr++) {
             next=*ptr-'0'; step=KeijiStep[keiji][next];
             if (step==INF) break;
             else if (step>Max) { Max=step; MaxNext=next; }
         }
         if (*ptr==0) {
             ThiefStep[keiji][thief]=(char)(Max+1);
             NextThief[keiji][thief]=(char)MaxNext;
         }
     }
}

/*┌────────────────────┐
 │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(); long i,num;

    if (argc==2) num=atol(argv[1]); else num=1;
    for (i=0;i<num;i++) for (Initialize();MoveKeiji();MoveThief()) ;
    Print();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}