/*
2001/07 タンク・チェンジ
coded by Isaku WADA
 ┌───────────────────────────────┐
 │ Fig.2のような盤を用意し,A軍の戦車3台とB軍の戦車3 │
 │台をそれぞれ1,2,3と16,17,18の円に配置する。直線 │
 │は道路を,円は広場を表す。                  │
 │                               │
 │ 1.A軍を先手として,3台の戦車のうちのどれかを1台動かす。│
 │   これを交互に繰り返す                  │
 │                               │
 │ 2.戦車は道路に沿って広場から広場へと移動できる。1つの広 │
 │   場には1台しか入れない                 │
 │                               │
 │ 3.戦車は動き始めたら止まるまで直進しかできない。いくつ先 │
 │   の広場で止まるかは自由だが,通り道にほかの戦車がいる場 │
 │   合はそれより先には進めない。いくつ進んでもこれが「1手」│
 │                               │
 │ 4.止まった広場が敵軍の戦車から道路を介してまっすぐに見え │
 │   る場合には,撃たれてしまう               │
 │                               │
 │ 以上の条件で,両軍が撃ち合うことなく戦車をそっくり入れ替え │
 │たい(A軍とB軍がそれぞれ16,17,18と1,2,3にある │
 │状態にしたい)。最低何手で完成できるだろうか。その移動手順の │
 │一例も示すこと。                       │
 │                               │
 │Fig.2 タンク・チェンジの盤面              │
 │                               │
 │  1   6   11   16                │
 │   \ / \ / \ /                 │
 │    4   9   14                  │
 │   / \ / \ / \                 │
 │  2   7   12   17                │
 │   \ / \ / \ /                 │
 │    5   10   15                  │
 │   / \ / \ / \                 │
 │  3   8   13   18                │
 └───────────────────────────────┘

 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │キューとハッシングを用いた幅優先探索で解きます。      │
 │                              │
 │ 盤の状態はA軍B軍のそれぞれについて3台の戦車の位置で表し│
 │ます。位置はビットの和で表します。例えばA軍の初期位置は1,│
 │2,3なので、A軍の状態は2+4+8と表します。同様にB軍の│
 │初期位置は16,17,18なので、B軍の状態は65536+ │
 │131072+262144と表します。           │
 │                              │
 │ プログラムはA軍の状態、B軍の状態、何手目か、そして、親局│
 │面の番号を記録する4つのキューを持ち、最初に初期状態をこれら│
 │のキューに登録します。                   │
 │                              │
 │ メインループは、キューから情報を取り出して、それを一手だけ│
 │先に進めた状態を全て生成し、新しい状態ならば、それをキューに│
 │追加するという作業を繰り返します。奇数手の時はA軍を動かし、│
 │偶数手の時はB軍を動かします。               │
 │                              │
 │ メインループで、新たな状態がA軍とB軍が入れ替わった状態に│
 │なったら親局面の番号をたどりながら、盤の状態を表示して、プロ│
 │グラムを終了させます。                   │
 └──────────────────────────────┘
*/

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

/*┌─────┐
 │定数の宣言│
 └─────┘*/
#define S       18                         /* 広場の数 Square  */
#define L        8                         /* 道路の数 Line    */
#define C        4                         /* 表示の時並べる数 */
#define N     2690                         /* 作業領域の大きさ */
#define T(X) (1L<<(X))                     /* ビット表現へ変換 */
#define A    (T( 1)+T( 2)+T( 3))           /* A軍の初期位置   */
#define B    (T(16)+T(17)+T(18))           /* B軍の初期位置   */
#define M(X)  T(X)&a?"A":T(X)&b?"B":"×" /* 表示用の文字列   */

/*┌────────────────────────────┐
 │道路上の広場は等差数列なので、初期値・公差・終了値で表す│
 └────────────────────────────┘*/
struct { long bits; int top,diff,end; } Line[L] =
{ {0L,1,3,13},{0L,2,2, 6},{0L, 2,3, 8},{0L, 3,2,11},
  {0L,6,3,18},{0L,8,2,16},{0L,11,3,17},{0L,13,2,17} };

/*┌─────┐
 │変数の宣言│
 └─────┘*/
unsigned long Area[S+1]; /* 与えられた点から撃てる範囲   */
unsigned long PosAQ[N];  /* A軍の位置を記録するキュー   */
unsigned long PosBQ[N];  /* B軍の位置を記録するキュー   */
int StepQ[N];     /* 何手目かを記録するキュー     */
int PrevQ[N];     /* 親局面の番号を記録するキュー */
int HashTable[N]; /* ハッシュ・テーブル           */
int HashNext[N];  /* 同じハッシュ値を持つ次の要素 */ 
int QHead,QTail,QTail2;

/*┌────────┐
 │マップを書き出す│
 └────────┘*/
void Print(long a,long b)
{
    static int c; static char buf[100];

#if defined(__CYGWIN__) || defined(UNIX)
    printf("\x1b[2J");
#else
    system("CLS");
#endif
    printf("%3d ",c++);
    printf(    "%s  %s  %s  %s \n",   M(1),M(6),M(11),M(16) );
    printf("      %s  %s  %s   \n",     M(4), M(9),M(14)    );
    printf("    %s  %s  %s  %s \n",   M(2),M(7),M(12),M(17) );
    printf("      %s  %s  %s   \n",     M(5),M(10),M(15)    );
    printf("    %s  %s  %s  %s \n\n", M(3),M(8),M(13),M(18) );
    printf(" > "); fgets(buf,sizeof buf,stdin);
}

/*┌─────────────────┐
 │再帰呼び出しをして、手順を書き出す│
 └─────────────────┘*/
void Print1(int x)
{
    if (x) Print1(PrevQ[x]);
    Print(PosAQ[x],PosBQ[x]);
}

/*┌─────────────────┐
 │再帰呼び出しをして、手順を書き出す│
 └─────────────────┘*/
void Print2(int x)
{
    Print(PosBQ[x],PosAQ[x]);
    if (x) Print2(PrevQ[x]);
}

/*┌──────┐
 │パズルを解く│
 └──────┘*/
int Solve(void)
{
    int  HashValue,Step,Diff,i,j,k;
    unsigned long Tanks,Enemies,Occupied,Range,NewTanks,NewA,NewB;

    /* 配列の初期化 */
    for (i=0;i<N;i++) HashTable[i]=-1;
    for (j=0;j<L;j++)
     for (i=Line[j].top;i<=Line[j].end;i+=Line[j].diff)
         Line[j].bits|=T(i);
    for (i=1;i<=S;i++) for (j=0;j<L;j++)
     if (Line[j].bits&T(i)) Area[i]|=Line[j].bits;

    /* 初期状態をキューに登録する */
    PosAQ[0]=A; PosBQ[0]=B; StepQ[0]=0; QTail=1;

    /* メイン・ループ */
    /* キューが空になるまで幅優先探索を繰り返す */
    for (QHead=0;QHead<QTail;QHead++) {

        /* キューからデータを取り出す */
        /* 奇(偶)数手ならA(B)軍を味方として動かす */
        Step=StepQ[QHead]+1;
        if (Step&1) { Tanks=PosAQ[QHead]; Enemies=PosBQ[QHead]; }
        else        { Tanks=PosBQ[QHead]; Enemies=PosAQ[QHead]; }

        Occupied=0; /* 敵軍の攻撃範囲をOccupiedに求める */
        for (i=1;i<=S;i++) if (Enemies&T(i)) Occupied|=Area[i];

        /* 3つの味方戦車(Tanks)について繰り返す(i) */
        for (i=1;i<=S;i++) if (Tanks&T(i)) {

            /* 選んだ戦車の行動範囲をRangeに求める */
            Range=Area[i]&~Occupied&~Tanks;

            /* Rangeのうち、途中に他の戦車がある場所を取り除く */
            for (j=1;j<=S;j++) if (Range&T(j)) {
                for (k=0;k<L;k++) /* iとjを含む道路をkに求める */
                    if (Line[k].bits&T(i)&&Line[k].bits&T(j)) break;
                if (j>i) Diff=Line[k].diff; else Diff=-Line[k].diff;
                for (k=i+Diff;k!=j;k+=Diff)
                    if (Tanks&T(k)||Enemies&T(k)) Range&=~T(j);
            }

            /* 味方(i)の行動範囲(Range)について繰り返す(j) */
            for (j=1;j<=S;j++) if (Range&T(j)) {

                /* 動かした結果の味方全員の位置をNewTanksに求める */
                NewTanks=(Tanks&~T(i))|T(j);

                /* 奇(偶)数手ならA(B)軍を新しくする */
                /* NewA と NewB によって新しい局面を表す */
                if (Step&1) { NewA=NewTanks; NewB=Enemies; }
                else        { NewB=NewTanks; NewA=Enemies; }

                /* 過去に局面が出現したかどうか */
                HashValue=(int)(((NewA*(NewB+12345))>>16)%N);
                for (k=HashTable[HashValue];k!=-1;k=HashNext[k])
                    if (PosAQ[k]==NewA&&PosBQ[k]==NewB) break;
                if (k!=-1) continue; /* 既にあるので次へ */

                if (QTail>=N) { printf("Nが小さい\n"); return 1; }

                /* キューに局面を登録する */
                PosAQ[QTail]=NewA;  PosBQ[QTail]=NewB;
                PrevQ[QTail]=QHead; StepQ[QTail]=Step;

                /* ハッシュ・テーブルに登録する */
                HashNext[QTail]=HashTable[HashValue];
                HashTable[HashValue]=QTail; QTail++;

                /* 終了条件が成立したら手順を書き出して終了する */
                HashValue=(int)(((NewB*(NewA+12345))>>16)%N);
                for (k=HashTable[HashValue];k!=-1;k=HashNext[k])
                    if (PosAQ[k]==NewB&&PosBQ[k]==NewA) break;
                if (k!=-1) { QTail2=PrevQ[k]; return 0; }
            }
        }
    }
    printf("解が見つからない\n"); return 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(void)
{
   char buf[100]; double start=clock();

   if (Solve()) return 1;
   printf("%9.3f秒 > ",(clock()-start)/CLOCKS_PER_SEC);
   fgets(buf,sizeof buf,stdin);
   Print1(QTail-1); Print2(QTail2);return 0;
}