/*
2002/09 くろ交換しろ
coded by Isaku WADA
 ┌───────────────────────────┐
 │ Fig.2のようなマスが描かれた盤があり,そのマスに白・│
 │黒のコマそれぞれ3個が置かれている。このFig.2の状態か│
 │らコマを順次動かして,白と黒のコマの場所を入れ替えたい│
 │(Fig.3の状態にしたい)。コマを移動する際の条件は以下の│
 │とおり。                       │
 │ (1)コマは常にマス内に存在し,各マスには1つしかコマ│
 │   は入れない                   │
 │ (2)あるコマの隣のマスが空いていれば移動できる。隣と│
 │   とは上下左右のマスを指し,斜めは考えない    │
 │ (3)コマがほかのマスに移動するとそれを一手と数える。│
 │   ただし,同じコマが連続して移動する場合は,止まる│
 │   までをまとめて1手とする            │
 │ この条件で,最低何手で完成できるだろうか。「盤全体を│
 │180度回転する」なんていうのは,ここでは考えない。 │
 │                           │
 │ Fig.2 入れ替える前   Fig.3入れ替えたあと   │
 │         □            □    │
 │         ●            ○    │
 │         ●            ○    │
 │       □○●□         □●○□   │
 │        ○            ●     │
 │        ○            ●     │
 │        □            □     │
 │                           │
 └───────────────────────────┘
 ┌─────┐
 │解答:22手│
 └─────┘
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.003609秒│ 45056 byte │
 │Microsoft Visual C++ .NET  │0.003296秒│ 49152 byte │
 │Borland C++ 5.5 for Win32  │0.003938秒│ 59392 byte │
 │gcc-2.953(djgpp)      │0.003407秒│ 162817 byte │
 │gcc-2.953(cygwin)      │0.003203秒│ 20920 byte │
 │LSI C-86 Ver 3.30 試食版  │0.009800秒│ 15875 byte │
 │Turbo C Ver 1.5(small model)│0.051700秒│ 13688 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │   OS:Windows XP   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │キューとハッシュ法を用いた幅優先探索で解きました。     │
 │                              │
 │メモリを節約するために、キューに登録するデータは、配置を10│
 │×2ビットへ圧縮した整数にしました。ハッシュ関数もこの整数値│
 │を利用します。                       │
 │                              │
 │プログラムはまず、初期配置をキューに登録します。次に、キュー│
 │から配置を取り出し、親配置とします。そして、その配置から1手│
 │で到達できる配置のうち新しいものをキューに追加してゆきます。│
 │このとき、新しい配置のメンバpathに親配置のインデックスを記録│
 │しておき、後で辿れるようにしておきます。新しい配置が条件を満│
 │たしていれば探索は終了します。そうなるまで、キューから親配置│
 │を取り出し、一連の作業を繰り返してゆきます。        │
 │                              │
 │高速化のため、配置を登録するときにハッシュ法を使って、過去に│
 │同じ配置が出現していないかどうかを調べています。      │
 │                              │
 │なお、親配置から1手進んだ新しい配置を得るときには、まず、4│
 │つの空白について繰り返し、さらに、それぞれに対して、行き止ま│
 │りへ向かう4つのルートについて繰り返します。そこで、選ばれた│
 │空白から、選ばれたルートへ進んで初めて現れたコマを、選ばれた│
 │空白の上へ移動します。このとき、複数のルートで現れたコマの位│
 │置が共通の場合は、探索しても無駄なので、あらかじめヒストリー│
 │に登録しておくことにより、スキップするようにしてあります。 │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │圧縮した20ビットのデータを素数5003で割った余りをハッシ│
 │ュ関数にしました。圧縮とハッシュ関数を共通化したことが高速化│
 │の鍵となっています。実際に実験したところ、圧縮しない場合より│
 │も圧縮を行ったほうが高速になりました。           │
 └──────────────────────────────┘
*/

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

/*┌───────┐
 │定数・型の宣言│
 └───────┘*/
#define NUM_OF_EMPTY 4         /* 何も乗らないマスの数         */
#define MAX_ROUTE    4         /* ルートの最大数               */
#define NODE_SIZE 4200         /* プログラムが記録する状態の数 */
#define HASH_SIZE 5003         /* ハッシュテーブルの大きさ     */
enum {EMPTY,BLACK,WHITE};      /* マスの状態                   */
enum {A,B,C,D,E,F,G,H,I,J,SZ}; /* 各々のマスの位置(SZは総数)   */
typedef char map_t[SZ];        /* 盤の状態を記録する型         */

/*┌──────┐
 │盤の初期状態│
 └──────┘*/
map_t StartMap={
              EMPTY,
              BLACK,
              BLACK,
  EMPTY,WHITE,BLACK,EMPTY,
        WHITE,
        WHITE,
        EMPTY
};

/*┌──────┐
 │盤の終了状態│
 └──────┘*/
map_t EndMap={
              EMPTY,
              WHITE,
              WHITE,
  EMPTY,BLACK,WHITE,EMPTY,
        BLACK,
        BLACK,
        EMPTY
};

/*┌─────────────────┐
 │行き止まりへのルートを列挙したもの│
 └─────────────────┘*/
char*RouteTable[SZ][MAX_ROUTE]={
   /*           A */ {"BCFEHIJ","BCFED","BCFG",""  },
   /*     A    B */ {"CFEHIJ", "CFED", "CFG", "A" },
   /*     B    C */ {"FEHIJ",  "FED",  "FG",  "BA"},
   /*     C    D */ {"EFCBA",  "EHIJ", "EFG", ""  },
   /* DEFG  E */ {"FCBA",   "HIJ",  "FG",  "D" },
   /*   H      F */ {"EHIJ",   "CBA",  "ED",  "G" },
   /*   I      G */ {"FEHIJ",  "FCBA", "FED", ""  },
   /*   J      H */ {"EFCBA",  "EFG",  "ED",  "IJ"},
   /*           I */ {"HEFCBA", "HEFG", "HED", "J" },
   /*           J */ {"IHEFCBA","IHEFG","IHED",""  }
};

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

/*┌─────┐
 │変数の宣言│
 └─────┘*/
node_t NodeTable[NODE_SIZE]; /* ノード構造体の配列     */
int    HashTable[HASH_SIZE]; /* ハッシュ・テーブル     */
int    History[MAX_ROUTE];   /* 履歴を記録する         */
int    HistSize;             /* 履歴に溜まった数       */
int    QueueTail,QueueHead;  /* ノードのキュー         */
long   EndPack;              /* 終了状態を圧縮したもの */

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

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

/*┌─────────┐
 │盤の状態を圧縮する│
 └─────────┘*/
long Compress(map_t map)
{
    long r=0; int i;

    for (i=0;i<SZ;i++) r=(r<<2)+map[i];
    return r;
}

/*┌────────────┐
 │圧縮されたものを元に戻す│
 └────────────┘*/
void Uncompress(map_t map,long r)
{
    int i;

    for (i=SZ-1;i>=0;i--) { map[i]=(char)(r&3); r>>=2; }
}

/*┌─────┐
 │解答の表示│
 └─────┘*/
void PrintPath(int p)
{
    static char*s[]={"・","●","○"}; static int step;
    static unsigned char q[SZ];

    if (p) PrintPath(NodeTable[p].path);
#ifdef __CYGWIN__
    printf("\x1b[2J");
#else
#ifdef UNIX
    system("clear");
#else
    system("CLS");
#endif
#endif
    Uncompress((char*)q,NodeTable[p].stat);
    printf("%d:\n",step++);
    printf("   %s  \n",                s[q[A]]        );
    printf("   %s  \n",                s[q[B]]        );
    printf("   %s  \n",                s[q[C]]        );
    printf(" %s%s%s%s \n",s[q[D]],s[q[E]],s[q[F]],s[q[G]]);
    printf("  %s   \n",        s[q[H]]                );
    printf("  %s   \n",        s[q[I]]                );
    printf("  %s   \n",        s[q[J]]                );
    HitEnter();
}

/*┌────────────────────────┐
 │履歴に既に現れていれば1を返す。なければ登録する│
 └────────────────────────┘*/
int CheckHistory(int pos)
{
    int i;

    for (i=0;i<HistSize;i++) if (pos==History[i]) return 1;
    History[HistSize++]=pos; return 0;
}

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

    for (i=HashTable[hash];i!=-1;i=NodeTable[i].next)
     if (pack==NodeTable[i].stat) return 0;
    if (QueueTail>=NODE_SIZE) { printf("overflow"); exit(1); }
    NodeTable[QueueTail].stat=pack;
    NodeTable[QueueTail].next=HashTable[hash];
    HashTable[hash]=QueueTail;
    NodeTable[QueueTail].path=QueueHead;
    if (pack==EndPack) return 1; else { QueueTail++; return 0; }
}

/*┌───────────────┐
 │幅優先探索を使ってパズルを解く│
 └───────────────┘*/
void Solve(void)
{
    map_t map; int e,empty,route,k; char*p;

    /* データの初期化 */
    for (k=0;k<HASH_SIZE;k++) HashTable[k]=-1;
    EndPack=Compress(EndMap); QueueTail=0;
    SearchAndRegist(StartMap); /* 初期状態をキューに登録 */
    for (QueueHead=0;QueueHead<QueueTail;QueueHead++) {
        /* キューから状態を取り出す */
        Uncompress(map,NodeTable[QueueHead].stat);
        for (empty=e=0;e<NUM_OF_EMPTY;empty++,e++) {
            HistSize=0; /* 履歴の初期化 */
            while (map[empty]!=EMPTY) empty++; /* 空のマスを探す */
            for (route=0;route<MAX_ROUTE;route++) {
                /* 与えられたルートでの空でないマスを探す */
                p=RouteTable[empty][route];
                while (*p&&map[k=*p-'A']==EMPTY) p++;
                if (*p==0||CheckHistory(k)) continue;
                map[empty]=map[k]; map[k]=EMPTY;     /* 移動 */
                if (SearchAndRegist(map)) return;    /* 検査 */
                map[k]=map[empty]; map[empty]=EMPTY; /* 元に戻す */
            }
         }
    }
    printf("cannot solve"); 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(); long i,num;

    if (argc==2) num=atol(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;
}