/*
2002/07 RUSH HOUR
coded by Isaku WADA
 ┌────────────────────────────┐
 │ 米国のバイナリ・アーツ社から出ている,「RUSH HO│
 │UR」というパズルから。                │
 │ Fig.3のように,6×6の広さの駐車場に車がぎっしりと入│
 │っている。アルファベットが書かれた2単位または3単位のピ│
 │ースが車を表し,灰色部はスキ間である。あなたの車(X)を,│
 │ほかの車をうまく移動させながら矢印の位置の出口から外に出│
 │したい。ただし,すべての車は前後(ピースの長手方向)にしか│
 │動けないこととする。最短何手で外に出られるか。車は中途半│
 │端な位置では止まらないで1コマ単位で移動し,また,同じ車│
 │が一度に何コマ移動しても止まるまでを1手と数える。   │
 │                            │
 │          Fig.3 RUSH HOUR          │
 │         ┏━┯━━━┯━┯━┯━┓      │
 │         ┃ │ A │■│ │■┃      │
 │         ┃ ├─┬─┤■│B├─┨      │
 │         ┃J│ │ │■│ │ ┃      │
 │         ┃ │C│D├─┴─┤ ┃      │
 │         ┃ │ │ │ X │K│→ 出口  │
 │         ┠─┴─┴─┼─┬─┤ ┃      │
 │         ┃  L  │ │■│ ┃      │
 │         ┠───┬─┤E├─┴─┨      │
 │         ┃■■■│ │ │ G ┃      │
 │         ┠───┤F├─┴─┬─┨      │
 │         ┃ H │ │ I │■┃      │
 │         ┗━━━┷━┷━━━┷━┛      │
 └────────────────────────────┘
 ┌──────┐
 │解答:51手│
 └──────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00981 秒│ 45056 byte │
 │Microsoft Visual C++ .NET  │0.01004 秒│ 49152 byte │
 │Borland C++ 5.5 for Win32  │0.01500 秒│ 59904 byte │
 │gcc-2.953(djgpp)      │0.01153 秒│ 163257 byte │
 │gcc-2.953(cygwin)      │0.01131 秒│ 21360 byte │
 │LSI C-86 Ver 3.30 試食版  │0.03290 秒│ 15941 byte │
 │Turbo C Ver 1.5(small model)│0.05778 秒│ 13678 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │キューとハッシュ法を用いた幅優先探索で解きました。     │
 │                              │
 │メモリを節約するために、キューに登録するデータは6×6の行列│
 │ではなく、13台の車の位置にしました。例えば、車Aは一番上の│
 │行中でしか移動しないので、横方向の位置だけを覚えておけば大丈│
 │夫です。しかも、位置は0〜4の値しかとらないので1バイトで2│
 │台の車の位置を覚えることができます。従って13台全ての車の配│
 │置を、たったの7バイトで記録することができます。      │
 │                              │
 │プログラムはまず、初期配置をキューに登録します。次に、キュー│
 │から配置を取り出し、親配置とします。そして、その配置から1手│
 │で到達できる配置のうち新しいものをキューに追加してゆきます。│
 │このとき、新しい配置のメンバpathに親配置のインデックスを記録│
 │しておき、後で辿れるようにしておきます。新しい配置で車Xが一│
 │番左に移動できていれば探索は終了します。そうなるまで、キュー│
 │から親配置を取り出し、一連の作業を繰り返してゆきます。   │
 │                              │
 │高速化のため、配置を登録するときにハッシュ法を使って、過去に│
 │同じ配置が出現していないかどうかを調べています。      │
 │                              │
 │なお、親配置から新しい配置を得るときには、まず、7つの空白に│
 │ついて繰り返し、さらに、それぞれに対して、4方向について繰り│
 │返します。そこで、選ばれた空白から、選ばれた方向を向いて見え│
 │る車を、選ばれた空白の上へ可能なら移動します。       │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │メモリを節約したため、LSI−C試食版でも実行できるようにな│
 │りました。512Mbyteのメモリを実装しているマシンを使っているの│
 │に、データを64Kbyteに収めるために四苦八苦するのは滑稽ですが │
 │、移植性を高める努力は、今後も続けてゆきたいと思います。  │
 └──────────────────────────────┘
*/

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

/*┌───────┐
 │定数・型の宣言│
 └───────┘*/
#define SX 6 /* 駐車場の大きさ */
#define SY 6
#define NODE_SIZE 3025 /* プログラムが記録する配置の数 */
#define HASH_BITS   13 /* ハッシュ・テーブルの大きさ */
#define HASH_SIZE (1<<HASH_BITS)
enum { A,B,C,D,E,F,G,H,I,J,K,L,X,Z }; /* Z は車数と空白を表す */
typedef char map_t[SY][SX];     /* 駐車場の配置を表現した配列 */
typedef char pack_t[(Z-1)/2+1]; /* 駐車場の配置を圧縮した配列 */

/*┌────┐
 │盤の宣言│
 └────┘*/
map_t StartMap={  /* 駐車場の初期配置 */
    {J,A,A,Z,B,Z},
    {J,C,D,Z,B,K},
    {J,C,D,X,X,K},
    {L,L,L,E,Z,K},
    {Z,Z,F,E,G,G},
    {H,H,F,I,I,Z}
};

/*┌───────────────────────────┐
 │車が持つ固有情報の構造体(圧縮・展開で使う。変化しない)│
 └───────────────────────────┘*/
typedef struct {
    char dir; /* 車の方向(0:横 1:縦)                  */
    char len; /* 車の長さ(2か3)                       */
    char pos; /* 車の固定された位置(横向きなら縦の位置) */
}info_t;

info_t CarData[Z]={  /* A〜X までの車の固有情報(変化しない) */
    {0,2,0},{1,2,4},{1,2,1},{1,2,2},{1,2,3},{1,2,2},{0,2,4},
    {0,2,5},{0,2,5},{1,3,0},{1,3,5},{0,3,3},{0,2,2}
};

/*┌──────────────────────┐
 │配置とハッシュ表に関する情報を記録する構造体│
 └──────────────────────┘*/
typedef struct {
    pack_t stat; /* 駐車場の配置                       */
    int    next; /* ハッシュテーブルからのリストを表す */
    int    path; /* 逆順のパスを記録する               */
}node_t;

/*┌─────┐
 │変数の宣言│
 └─────┘*/
node_t NodeTable[NODE_SIZE]; /* ノード構造体の配列 */
int    HashTable[HASH_SIZE]; /* ハッシュ・テーブル */
int    QueueTail,QueueHead;  /* ノードのキュー     */

/*┌───────────┐
 │駐車場の配置を圧縮する│
 └───────────┘*/
void CompressMap(pack_t to,map_t from)
{
    int i,j,t;

    for (t=0;t<Z;t++) {
        i=0; j=CarData[t].pos;
        if (CarData[t].dir) while (from[i][j]!=t) i++;
        else                while (from[j][i]!=t) i++;
        if ((t&1)==0) to[t>>1]=(char)i; else to[t>>1]|=i<<4;
    }
}

/*┌───────────┐
 │駐車場の配置を展開する│
 └───────────┘*/
void UncompressMap(map_t to,pack_t from)
{
    int i,j,t,k;

    for (i=0;i<SY;i++) for (j=0;j<SX;j++) to[i][j]=Z;
    for (t=0;t<Z;t++) {
        if (t&1) i=(from[t>>1]>>4)&15; else i=from[t>>1]&15;
        j=CarData[t].pos; k=CarData[t].len;
        if (CarData[t].dir) for (;k;k--) to[i++][j]=(char)t;
        else                for (;k;k--) to[j][i++]=(char)t;
    }
}

/*┌─────────────┐
 │改行キーが押されるまで待つ│
 └─────────────┘*/
void HitEnter(void)
{
    char buf[100];

    printf("\n HIT [ENTER] KEY > ");
    fgets(buf,sizeof buf,stdin);
}

/*┌─────┐
 │解答の表示│
 └─────┘*/
void PrintPath(int p)
{
    static char str[]="ABCDEFGHIJKLX ";
    static int x,y,step; static map_t map;

    if (p) PrintPath(NodeTable[p].path);
#ifdef __CYGWIN__
    printf("\x1b[2J");
#else
#ifdef UNIX
    system("clear");
#else
    system("CLS");
#endif
#endif
    printf("%d:\n",step++); UncompressMap(map,NodeTable[p].stat);
    for (y=0;y<SY;y++) {
        for (x=0;x<SX;x++) printf("%.2s",str+map[y][x]*2);
        printf("\n");
    }
    HitEnter();
}

/*┌─────────────────────────────┐
 │選ばれた空白(x,y)から、選ばれた方向(dir)を向いて見えた車を│
 │(x,y)へ移動する。移動できれば1返す。できなければ0を返す。 │
 │dir=0:右,  dir=1:左,  dir=2:下,  dir=3:上         │
 └─────────────────────────────┘*/
int MoveCar(map_t map,int x,int y,int dir)
{
    int n,i,car=Z,d=dir&1?-1:1;

    if (dir<2) {
        for (n=x+d;n>=0&&n<SX&&(car=map[y][n])==Z;n+=d) ;
        if (car==Z||CarData[car].dir) return 0;
        for (i=CarData[car].len;i;i--)
        { map[y][n]=Z; map[y][x]=(char)car; n+=d; x+=d; }
    }else{
        for (n=y+d;n>=0&&n<SY&&(car=map[n][x])==Z;n+=d) ;
        if (car==Z||CarData[car].dir==0) return 0;
        for (i=CarData[car].len;i;i--)
        { map[n][x]=Z; map[y][x]=(char)car; n+=d; y+=d; }
    }
    return 1;
}

/*┌──────┐
 │ハッシュ関数│
 └──────┘*/
int HashFunc(map_t map)
{
    unsigned long*p=(unsigned long*)map,h=0; int i;

    for (i=0;i<sizeof(map_t)/sizeof(unsigned long);i++) h^=p[i]>>i;
    return(int)((h*h)>>(32-HASH_BITS));
}

/*┌───────────────────────────┐
 │配置が既にハッシュテーブルに登録されていれば何もしない│
 │配置が新しいものであれば、ハッシュテーブルに登録する │
 │終了条件を満たしていれば1を返す           │
 └───────────────────────────┘*/
int SearchAndRegist(map_t map)
{
    int i,h=HashFunc(map); pack_t pack;

    CompressMap(pack,map);
    for (i=HashTable[h];i!=-1;i=NodeTable[i].next)
     if (memcmp(pack,NodeTable[i].stat,sizeof pack)==0) return 0;
    if (QueueTail>=NODE_SIZE) { printf("overflow.\n"); exit(1); }
    memcpy(NodeTable[QueueTail].stat,pack,sizeof pack);
    NodeTable[QueueTail].next=HashTable[h]; HashTable[h]=QueueTail; 
    NodeTable[QueueTail].path=QueueHead;
    if (map[2][5]==X) return 1; else { QueueTail++;  return 0; }
}

/*┌───────────────┐
 │幅優先探索を使ってパズルを解く│
 └───────────────┘*/
void Solve(void)
{
    map_t map,temp; int i,x,y,dir;

    for (i=0;i<HASH_SIZE;i++) HashTable[i]=-1;
    QueueTail=0; SearchAndRegist(StartMap);
    for (QueueHead=0;QueueHead<QueueTail;QueueHead++) {
        UncompressMap(temp,NodeTable[QueueHead].stat);
        memcpy(map,temp,sizeof map);
        for (y=0;y<SY;y++) for (x=0;x<SX;x++) if (map[y][x]==Z)
         for (dir=0;dir<4;dir++) if (MoveCar(map,x,y,dir)) {
             if (SearchAndRegist(map)) return;
             memcpy(map,temp,sizeof map);
         }
    }
    printf("cannot solve.\n"); exit(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(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    HitEnter(); PrintPath(QueueTail);
    return 0;
}