/*
2000/11 H2O
coded by Isaku WADA
 ┌────────────────────────────┐
 │ Fig. 3のように,机の上に8個のコインをH型に並べた。これ│
 │をFig. 4のようにO型にしたい。              │
 │ まず1個のコインを選び,もち上げないで机の表面を滑らせ │
 │る。もちろんこのときほかのコインを動かしてはいけない。そ│
 │して位置がはっきりと決まる(つまり2個以上のコインと接する│
 │)ところまで移動する。これで一手だ。完成までの最少手数と │
 │その手順をお答えいただきたい。             │
 │ なお,2個と接するとはいっても,1個ぶんの間隔をあけた2 │
 │個のコインの間に差し込むという動きは,位置がうまく決まら│
 │ないので不可とする。余裕のある方はOからHへ戻すほうも挑戦│
 │していただきたい。                   │
 │                            │
 │  ●  ●       ●●●            │
 │  ●●●●       ● ●            │
 │  ●  ●       ●●●            │
 │  Fig.3 H型     Fig.4 O型          │
 │                            │
 └────────────────────────────┘
*/

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

enum { X=4,Y=3,HASH_BITS=9,HASH_SIZE=1<<HASH_BITS,DATA_SIZE=479 };

char Start[Y][X]=
{{1,0,0,1}, /* 局面 */
 {1,1,1,1},
 {1,0,0,1}};

char Finish[Y][X]=
{{1,1,1,0}, /* 終了局面 */
 {1,0,1,0},
 {1,1,1,0}};

char Map[Y][X];      /* ゲームボード   */
int Data[DATA_SIZE]; /* 圧縮したデータ */
int Next[DATA_SIZE]; /* 同じハッシュ値を持つ次の要素 */
int Prev[DATA_SIZE]; /* 自分の親局面を示すポインタ   */
int Hash[HASH_SIZE]; /* ハッシュ表       */
int Qhead;           /* キューの先頭位置 */
int Qtail;           /* キューの後ろ位置 */

/*┌───────┐
 │状態を表示する│
 └───────┘*/
void PrintMap(int f)
{
    int i,j; static char buf[Y][81]; static int col;

    for (i=0;i<Y;i++) {
        for (j=0;j<X;j++)
            sprintf(buf[i]+strlen(buf[i]),Map[i][j]?"●":"  ");
        sprintf(buf[i]+strlen(buf[i]),"   ");
    }
    if (++col==7||f) {
        for (i=0;i<Y;i++) { printf("%s\n",buf[i]); buf[i][0]=0; }
        col=0; printf("\n");
    }
}

/*┌─────────────────┐
 │再帰呼び出しを使って手順を表示する│
 └─────────────────┘*/
int Display(int ptr,int f)
{
    static int count; int board,i,j,k;

    if (Prev[ptr]) count=Display(Prev[ptr],0);
    board=Data[ptr];
    for (i=k=0;i<Y;i++) for (j=0;j<X;j++)
        Map[i][j]=(board&(1<<k++))!=0;
    PrintMap(f);
    return count+1;
}

/*┌───────────────────────┐
 │局面が新しければハッシュ表に登録しコードを返す│
 │局面が既に登録されていれば、0 を返す          │
 └───────────────────────┘*/
int Search(void)
{
    int i,j,k,board,p,h; unsigned long hh;

    for (board=i=k=0;i<Y;i++) for (j=0;j<X;j++)
        board|=Map[i][j]<<k++;
    hh=board; h=(int)((hh*hh)>>(32-HASH_BITS));
    for (p=Hash[h];p;p=Next[p])
        if (board==Data[p]) return 0;
    if (Qtail>=DATA_SIZE)
    { printf("DATA_SIZE が足りない\n"); exit(1); }
    Prev[Qtail]=Qhead; Data[Qtail]=board;
    Next[Qtail]=Hash[h]; Hash[h]=Qtail++; return board;
}

/*┌──────────────────────────┐
 │コイン(i,j) が四方を囲まれて、動けなければ 1 を返す │
 └──────────────────────────┘*/
int Fix(int i,int j)
{
    if (i<Y-1&&i>0&&j<X-1&&j>0)
     if (Map[i+1][j]&&Map[i-1][j]&&Map[i][j+1]&&Map[i][j-1])
         return 1;
    return 0;
}

/*┌─────────────────┐
 │待ち行列(キュー)を使った幅優先探索│
 └─────────────────┘*/
void Solve(void)
{
    int u,v,i,j,k,board,end;

    for (i=0;i<Y;i++) for (j=0;j<X;j++) Map[i][j]=Start[i][j];
    for (i=0;i<HASH_SIZE;i++) Hash[i]=0;
    for (end=i=k=0;i<Y;i++) for (j=0;j<X;j++)
        end|=Finish[i][j]<<k++;
    Qhead=0; Qtail=1; Search();
    for (Qhead=1;Qhead<Qtail;Qhead++) {
        board=Data[Qhead];
        for (i=k=0;i<Y;i++) for (j=0;j<X;j++)
            Map[i][j]=(board&(1<<k++))!=0;
        for (u=0;u<Y;u++) for (v=0;v<X;v++) {
            if (Map[u][v]==0||Fix(u,v)) continue;
            Map[u][v]=0;
            for (i=0;i<Y;i++) for (j=0;j<X;j++) {
                if ((i==u&&j==v)||Map[i][j]||Fix(i,j)) continue;
                if (  (i==0||Map[i-1][j]==0)
                    &&(i==Y-1||Map[i+1][j]==0)) continue;
                if (  (j==0||Map[i][j-1]==0)
                    &&(j==X-1||Map[i][j+1]==0)) continue;
                Map[i][j]=1;
                if (Search()==end) return;
                Map[i][j]=0;
            } 
            Map[u][v]=1;
        }
    }
    printf("解がありません  ");  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("最小手数:%d  ",Display(Qtail-1,1)-1);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}