/*
2001/05 REV STAR
coded by Isaku WADA
 ┌─────────────────────────────┐
 │Fig. 1のように,星型が描かれた盤がある。その頂点と交点には│
 │黒丸が描かれており,この10か所の黒丸のうち,9か所に10円玉 │
 │を表向きにして置く(Fig.2)。これをスタートとして,以下のル │
 │ールで10円玉を移動していく。               │
 │ 1.1か所空いた場所(黒丸)に移動できる10円玉は,ほかの1枚あ│
 │  るいは2枚 の10円玉を跳び越してくるもののみ      │
 │ 2.跳び越しは線に沿って直線状に行われ,曲がり跳びは許され│
 │  ない                         │
 │ 3.跳び越された10円玉は裏返される(表向きだったものは裏向 │
 │  きに,裏向きだったものは表向きになる)。跳び越した10円 │
 │  玉の向きは,そのまま                 │
 │ さて,上記の操作を繰り返してすべての10円玉を表向きにする│
 │ には,1回の10円玉の移動を1手と数えるとすると,最低何手必│
 │ 要だろうか。もちろん,10円玉は黒丸以外の場所に移動できな│
 │ いし,1か所に2枚以上重ねることもできない。       │
 │                             │
 │Fig.1                           │
 │   ●                          │
 │                             │
 │● ●● ●                       │
 │  ● ●                         │
 │   ●                          │
 │ ●  ●                        │
 │                             │
 └─────────────────────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │   0                           │
 │                              │
 │1 23 4                        │
 │  5 6                          │
 │   7                           │
 │ 8  9                         │
 │                              │
 │  図1                          │
 │                              │
 │盤の各点に図1のように番号を付けます。そして、盤の状態は14│
 │ビットの整数であらわします。状態の下位10ビットは各点につい│
 │て表裏(0〜1)をあらわします。点が表なら1で、裏か空なら0で│
 │す。状態の上位4ビットは空の点の位置(0〜9)をあらわします。│
 │                              │
 │行列AdjMat[][]は、空の点を移動したときに反転する点のビットを│
 │あらわす行列です。第1インデックスで古い空の番号、第2インデ│
 │ックスで新しい空の番号を指定します。0なら移動できません。 │
 │                              │
 │アルゴリズムは待ち行列を使った幅優先探索です。初期値は、0番│
 │を除く全ての点が表なので、第0ビットが0、第1〜第9ビットが│
 │1、上位4ビットが0、すなわち1022とします。終了状態は、│
 │全ての点が裏か空なので、第0〜第9ビットが全て0となる状態で│
 │す。このとき上位4ビットは無視します。           │
 │                              │
 │アルゴリズムは、具体的には以下のようになります。      │
 │                              │
 │手順1:待ち行列に初期値を登録します。           │
 │手順2:待ち行列から状態を1つ取り出します。        │
 │手順3:移動可能な全ての空の点について、移動し、手順4を実行│
 │    します。                      │
 │手順4:移動した結果終了状態であれば、親状態をたどって結果を│
 │    表示し、終了します。終了状態でなければ、親状態を記録│
 │    して、待ち行列に登録します。            │
 │手順5:手順2へ戻ります。                 │
 └──────────────────────────────┘
 ┌──────────────────────────────┐
 │・感想                           │
 │                              │
 │毎号、色々なコンパイラで処理速度を比べていますが、今回はいつ│
 │もとは逆に、16ビットコンパイラのほうが32ビットコンパイラ│
 │よりも処理速度が速くなりました。Microsoft Visual C++ 6.0では│
 │0.00197秒なのに対しTurbo C Ver1.5では0.00154秒となりました。│
 └──────────────────────────────┘
    Visual C++, Borland C++, LSI C-86, Turbo C で動作確認
*/

#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

/*
盤の状態は14ビットの整数で表します。
状態の下位10ビットは各点について表裏(0〜1)を表します。
点が表なら1で、裏か空なら0です。
状態の上位4ビットは空の点の位置(0〜9)を表します。
*/
#define NUM 10              /* 点の数 */
#define SIZE ((1<<NUM)*NUM) /* 状態の最大値 */
#define W    5              /* 表示の時並べる数 */

/*
          A

     B  CD  E
        F  G
          H
       I    J
*/
enum { A=1,B=2,C=4,D=8,E=16,F=32,G=64,H=128,I=256,J=512};

/*
空の点を移動したとき反転する点のビットを表す行列です。
第1インデックスで古い空の番号、
第2インデックスでは新しい空の番号を指定します。
値が0なら移動できません。
*/
int AdjMat[NUM][NUM]=
 /*A*/ {{  0,  0, 0, 0,  0, C, D, 0,C+F,D+G},
 /*B*/  {  0,  0, 0, C,C+D, 0, 0, F,  0,F+H},
 /*C*/  {  0,  0, 0, 0,  D, 0, 0, 0,  F,  0},
 /*D*/  {  0,  C, 0, 0,  0, 0, 0, 0,  0,  G},
 /*E*/  {  0,C+D, D, 0,  0, 0, 0, G,G+H,  0},
 /*F*/  {  C,  0, 0, 0,  0, 0, 0, 0,  0,  H},
 /*G*/  {  D,  0, 0, 0,  0, 0, 0, 0,  H,  0},
 /*H*/  {  0,  F, 0, 0,  G, 0, 0, 0,  0,  0},
 /*I*/  {C+F,  0, F, 0,G+H, 0, H, 0,  0,  0},
 /*J*/  {D+G,F+H, 0, G,  0, H, 0, 0,  0,  0}};

int Prev[SIZE];  /* 一つ前の状態。-1 なら、まだ出現していない */
int Queue[SIZE]; /* 出現したが調べていない状態を表すキュー */

#define Z(X) ((stat>>NUM)==(X)?"・":(1<<(X))&stat?"○":"●")

/*┌─────────────────┐
 │再帰呼び出しをして、手順を書き出す│
 └─────────────────┘*/
void Print(int stat,int f)
{
    static char buf[6][81]; static int c,cnt,i;

    if (Prev[stat]) Print(Prev[stat],0);
    i=strlen(buf[1]); c++;
    sprintf(buf[0]+i," %3d  %s       ",cnt++, Z(0)         );
    sprintf(buf[1]+i,"               "                     );
    sprintf(buf[2]+i," %s  %s%s  %s  ",Z(1),Z(2),Z(3),Z(4) );
    sprintf(buf[3]+i,"    %s  %s     ",    Z(5),  Z(6)     );
    sprintf(buf[4]+i,"      %s       ",       Z(7)         );
    sprintf(buf[5]+i,"   %s    %s    ",  Z(8),      Z(9)   );
    if (c&&(f||c==W)) {
        for (i=0;i<6;i++) { printf("%s\n",buf[i]); buf[i][0]=0; }
        printf("\n\n"); c=0;
    }
}

/*┌──────┐
 │パズルを解く│
 └──────┘*/
void Solve(void)
{
    int i,head,tail,pos,curr,next;

    for (i=0;i<SIZE;i++) Prev[i]=-1;
    Prev[(1<<NUM)-2]=0; /* 初期状態をキューに登録する */
    Queue[0]=(1<<NUM)-2; tail=1;
    for (head=0;head<tail;head++) {
        pos=Queue[head]>>NUM; curr=Queue[head]&((1<<NUM)-1);
        for (i=0;i<NUM;i++) if (AdjMat[pos][i]) {
            next=(AdjMat[pos][i]^curr)|(i<<NUM);
            if (curr&(1<<i)) next=(next|(1<<pos))&~(1<<i);
            else next&=~(1<<pos);
            if (Prev[next]==-1) {
                Prev[next]=Queue[head];
                if ((next&(1<<NUM)-1)==0) { Print(next,1);return; }
                Queue[tail++]=next;
            }
        }
    }
}

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(void)
{
    double StartTime=clock();

    Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}