import java.applet.*;
import java.awt.*;
//---------------------------------------------------------
//  倉庫番を解く(Ver2.7)     written by Kenichiro Takahashi
//                     http://www.ic-net.or.jp/home/takaken
//                        (AppletSize width=400 height=364)
//---------------------------------------------------------
public class soko207 extends Applet implements Runnable {

final int X_MAX = 12;              // 横のサイズ
final int Y_MAX = 10;              // 縦のサイズ
final int K_MAX = 9;               // 荷物の最大個数
final int B_SIZE = 109987;         // バケットサイズ
final int Q_SIZE = 100000;         // キューサイズ
final int R_HASH = 491;            // 再ハッシュ増分
final int AREA = X_MAX*Y_MAX;      // マップの面積
final int DD = 30;                 // 単位長さ
final int diff[] = {-1,X_MAX,1,-X_MAX}; // 方向ベクトル

boolean  imgloaded = false;        // 画像読込完了
Graphics grf;                      // 画面定義
Image item[] = new Image[9];       // gif画像

Thread animation = null;           // アニメスレッド
int  IDX;                          // アニメポインタ
boolean animFlag = false;          // アニメモード
boolean editFlag = true;           // 編集モード
int  parts = 4;                    // 選択部品番号
int  ansMsg = 0;                   // 探索結果コード
int  thinkBar = 0;                 // 進行状況表示

int  disp_map[] = new int[AREA];   // 表示マップ
int  edit_map[] = new int[AREA];   // 編集マップ

//------ 以下、電子頭脳の作業用 ------------------

byte BACKET[][] = new byte[B_SIZE][K_MAX+1]; // 1,099,870 byte
int  LINK[]  = new int[B_SIZE];              //   439,948 byte
byte OPTN[]  = new byte[B_SIZE];             //   109,987 byte
int  QUEUE[] = new int[Q_SIZE];              //   400,000 byte

    // BACKET:局面の保存(荷物の位置と人の自由行動域先頭)
    // LINK  :どのパターンから派生したかリンク元アドレス
    // OPTN  :0:未定義  1:通常探索  2:逆解き探索  3,5:凍結しない局所パターン  4,6:凍結する局所パターン
    // QUEUE :幅優先探索用キュー(通常探索は0から,逆解き探索はQ_SIZE-1から逆へ)

int  Qtop1, Qend1, Qadd1, Qlen1;   // 通常探索用キューの各ポインタ
int  Qtop2, Qend2, Qadd2, Qlen2;   // 逆解き探索用キューの各ポインタ
int  chan, kara;                   // 通常探索と逆解き探索の衝突部連結
int  backetCnt, kosu, sift, bbun;
int  push, tesu, posS;

byte  main_map[] = new byte[AREA]; // 探索メインマップ 1:壁 2:荷物
byte  wall_map[] = new byte[AREA]; // 壁マップ         1:壁
byte  dead_map[] = new byte[AREA]; // デッドゾーン     1:デッド
byte  goal_map[] = new byte[AREA]; // ゴールマップ     1:格納地点
byte  pack_map[] = new byte[AREA]; // 開始荷マップ     1:開始時荷物
byte  work_map[] = new byte[AREA]; // 各種作業マップ
byte  hstb[] = new byte[K_MAX+1];  // 局面の圧縮データ(BACKET登録用)

//---------------------------------------------------------
// 初期処理
//---------------------------------------------------------
public void init() {
    setBackground(Color.gray);

    /* ボタン配置 */
    setLayout(new BorderLayout());
    Panel psouth = new Panel();
    psouth.add(new Button("CLEAR"));
    psouth.add(new Button("RESET"));
    psouth.add(new Button("START"));
    add("South", psouth);

    /* エディットマップ初期化 */
    initMap();
}
public void initMap() {             // 周辺を壁にする
    for (int i=0; i<AREA; i++)
        disp_map[i]=edit_map[i]=4;
    for (int y=1; y<Y_MAX-1; y++)
    for (int x=1; x<X_MAX-1; x++)
        disp_map[y*X_MAX+x] = edit_map[y*X_MAX+x] = 0;
}
public void resetMap() {           // 編集マップを表示マップへ
    for (int i=0; i<AREA; i++)
        disp_map[i] = edit_map[i];
}

//---------------------------------------------------------
// アニメーション処理
//---------------------------------------------------------
public void start() {
    if (animation == null) {
        animation = new Thread(this);
        animation.start();
    }
}
public void stop() {
    if (animation != null) {
        animation.stop();
        animation = null;
    }
}
public void run() {
    if (!imgloaded) {
        grf = getGraphics();
        repaint();

        /* gif画像ロード */
        MediaTracker tracker = new MediaTracker(this);
        for (int i=0; i<9; i++) {
            item[i] = getImage(getCodeBase(),"item"+i+".gif");
            tracker.addImage(item[i],0);
        }
        try {
            tracker.waitForAll(0);
            imgloaded = !tracker.isErrorAny();
        } catch (InterruptedException e) {}
        if (!imgloaded) {
            stop();
            grf.drawString("Image Load Error!", 10, 40);
            return;
        }
    }
    repaint();
    while (true) {
        try {
            if (animFlag) {
                int pAv = QUEUE[IDX++];   // キューをアニメ進行に併用
                if (pAv < 0) animFlag=false;
                else Moving(pAv,grf);     // 次のシーンを表示
            }
            animation.sleep(300);
        } catch (InterruptedException e) { stop(); }
    }
}
public void Moving(int pAv, Graphics g) {
    int posa, posb, posc, vect;

    vect = pAv % 10; pAv /= 10;        // 人の向き
    posb = pAv % 1000; pAv /= 1000;    // 移動先
    posa = pAv;                        // 移動元
    posc = posb + (posb - posa);       // 移動先の先

    disp_map[posa] = goal_map[posa];   // 移動元の人を消す
    drawParts(posa,g);
    if (disp_map[posb] > 1) {          // 移動先に荷物があれば
        disp_map[posc] += 2;           // その先に荷物を表示
        drawParts(posc,g);
        push++;                        // 荷押回数カウントアップ
    }
    disp_map[posb] = vect+5;           // 移動先に人を表示
    drawParts(posb,g);

    drawMsg(g);                        // 荷押回数表示
}

//---------------------------------------------------------
// 画面の表示
//---------------------------------------------------------
public void update(Graphics g) {       // ちらつき防止処理
    paint(g);
}
public void paint(Graphics g) {        // アプレット全体表示
    if (!imgloaded) {
        g.drawString("Now Image Loading...", 10, 20);
    } else {
        for (int posi=0; posi<AREA; posi++)          // マップ全体
            drawParts(posi, g);
        for (int i=0; i<6; i++)                      // パーツリスト
            g.drawImage(item[i],X_MAX*DD+6,i*(DD+6)+15,this);
        drawSelect(parts,Color.red,g);               // 選択パーツ□印
        drawBar(g);                                  // 探索進行バー
        drawMsg(g);                                  // メッセージ
    }
}
public void drawParts(int posi, Graphics g) {        // マップ内posi地点の表示
    int x, y, d;

    x = posi % X_MAX;
    y = posi / X_MAX;
    d = disp_map[posi];
    g.drawImage(item[d],x*DD,y*DD,this);
}
public void drawSelect(int p, Color c, Graphics g) { // 選択パーツ□印
    g.setColor(c);
    g.drawRect(X_MAX*DD+3,p*(DD+6)+12,DD+5,DD+5);
    g.drawRect(X_MAX*DD+4,p*(DD+6)+13,DD+3,DD+3);
}
public void drawBar(Graphics g) {                    // 探索進行バー
    g.setColor(Color.white);
    g.fillRect(0,Y_MAX*DD+1,(X_MAX+1)*DD+10,10);
    g.setColor(Color.red);
    for (int i=1; i<=thinkBar; i++)
        g.fillRect((i-1)*20+1,Y_MAX*DD+1,18,10);
}
public void drawMsg(Graphics g) {                    // メッセージ
    g.setColor(Color.white);
    g.fillRect(0,Y_MAX*DD+11,(X_MAX+1)*DD+10,23);
    g.setFont(new Font("Helvetica",Font.PLAIN,14));
    g.setColor(Color.black);
    switch (ansMsg) {
        case 1: g.drawString("Too many packages",DD,Y_MAX*DD+26); break;
        case 2: g.drawString("Strange mapping",  DD,Y_MAX*DD+26); break;
        case 3: g.drawString("Impossible !",     DD,Y_MAX*DD+26); break;
        case 4: g.drawString("Give up !",        DD,Y_MAX*DD+26); break;
        case 5: g.drawString("Now thinking",     DD,Y_MAX*DD+26); break;
        case 6: g.drawString("Push Count "+Integer.toString(push)+" / "+
                    Integer.toString(tesu),DD,Y_MAX*DD+26);
    }
}

//---------------------------------------------------------
// マウスイベント
//---------------------------------------------------------
public boolean mouseDown(Event e, int x, int y) {
    if (animFlag == false) {
        if (editFlag == false) {   // 解答アニメ終了直後ならRESET
            resetMap();
            ansMsg = thinkBar = 0;
            repaint();
            editFlag = true;
        }
        int ex = x / DD;
        int ey = y / DD;
        if (ex>0 && ex<(X_MAX-1) && ey>0 && ey<(Y_MAX-1)) { // 編集マップ部
            disp_map[ey*X_MAX+ex] = edit_map[ey*X_MAX+ex] = parts;
            drawParts(ey*X_MAX+ex,grf);
        } else if (x > X_MAX*DD) {
            int d = (y - 15) / (DD+6);
            if (d>=0 && d<=5 && d!=parts) {                 // 選択パーツ部
                drawSelect(parts,Color.gray,grf);
                parts = d;
                drawSelect(parts,Color.red ,grf);
            }
        }
    }
    return true;
}
public boolean action(Event e, Object arg) {
    if (e.target instanceof Button) {
        animFlag =false;
        if ("CLEAR".equals(arg)) {         // CLEARボタン
            initMap();
            ansMsg = thinkBar = 0;
            repaint();
            editFlag = true;
        } else
        if ("RESET".equals(arg)) {         // RESETボタン
            resetMap();
            ansMsg = thinkBar = 0;
            repaint();
            editFlag = true;
        } else
        if ("START".equals(arg)) {         // STARTボタン
            if (editFlag == false) return false;  // 2度押し防止
            ansMsg = 5;                           // Now thinking 表示
            drawMsg(grf);
            editFlag = false;
            computer();                           // 電子頭脳の起動
            drawMsg(grf);
            if (ansMsg == 6) {                    // 解を発見した
                IDX=0;
                animFlag=true;                    // 解答アニメ開始
            }
        }
    }
    return true;
}

//---------------------------------------------------------
// 以下、電子頭脳
//---------------------------------------------------------
//*********************************************************
//* アクティブゾーン(荷を押さずに自由行動可能域)調査      *
//*********************************************************
byte  h1map[] = new byte[AREA];   // 本探索  /荷押前
byte  h2map[] = new byte[AREA];   // 本探索  /荷押後
byte  b1map[] = new byte[AREA];   // 局所探索/荷押前
byte  b2map[] = new byte[AREA];   // 局所探索/荷押後
int   ac_top;                     // アクティブゾーンの先頭
int   ac_cnt;                     // アクティブゾーンの面積

/* (副関数)アクティブゾーンを再帰でposhから波状に調べる */
void active_zone_sub(byte actv_map[], int posh) {
    int posi, vect;

    actv_map[posh]=1;
    ac_cnt++;                           // 面積更新
    if (posh < ac_top) ac_top=posh;     // 先頭位置の更新
    for (vect=0; vect<4; vect++) {
        posi = posh + diff[vect];
        if (main_map[posi]==0 && actv_map[posi]==0)
            active_zone_sub(actv_map,posi);
    }
}

/* (主関数)アクティブゾーンをposhから調べactv_map[]に記録 */
int active_zone(byte actv_map[], int posh) {
    int i;

    ac_cnt=0;
    ac_top=AREA;
    for (i=X_MAX+1; i<AREA-X_MAX-1; i++) actv_map[i]=0;
    active_zone_sub(actv_map,posh);

    return ac_top;                      // 先頭位置を返す
}

//*********************************************************
//* デッドゾーン(進入禁止域調査)                          *
//*********************************************************
/* (副関数)荷物を置ける位置posiから再帰で波状に調べる */
void dead_zone_sub(int posi) {
    int posj, posk, vect;

    dead_map[posi]=0;
    for (vect=0; vect<4; vect++) {
        posj = posi + diff[vect];
        posk = posj + diff[vect];
        if (dead_map[posj]==1 && wall_map[posj]==0 && wall_map[posk]==0)
            dead_zone_sub(posj);             // 荷物を引っ張れるなら
    }
}

/* (主関数)荷物の進入可能位置を格納地点から調べる */
void dead_zone() {                           // 0:進入可能  1:進入禁止
    int  i;

    for (i=0; i<AREA; i++) dead_map[i]=1;
    for (i=0; i<AREA; i++)                   // 格納地点から調査
        if (goal_map[i]==1 && dead_map[i]==1) dead_zone_sub(i);
}

//*********************************************************
//* フリーズチェック(凍結検査)                            *
//*********************************************************
int  Fflag;  // 特例フラグ(凍結でも関連荷物総てが格納地点ならＯＫ)

/* (副関数)vectの直角方向にpospの荷物を移動可能か */
int  freeze_check_sub(int posp, int vect) {   // 返り値= 0:移動可 1:移動不可
    int pos1, pos2, retn=0;

    if (goal_map[posp] == 0) Fflag=1;  // 特例権利の喪失
    vect = (vect + 1) % 2;             // 方向を直角方向へ変換
    pos1 = posp - diff[vect];
    pos2 = posp + diff[vect];

    if (main_map[pos1]==1 || main_map[pos2]==1) return 1;  // どちらか壁
    if (dead_map[pos1]==1 && dead_map[pos2]==1) return 1;  // どちらもデッド

    main_map[posp] = 1;         // 堂々巡り防止の為荷物を一端壁にする
    if (main_map[pos1]==2 && freeze_check_sub(pos1,vect)==1) retn=1;
    else
    if (main_map[pos2]==2 && freeze_check_sub(pos2,vect)==1) retn=1;
    main_map[posp] = 2;         // 荷物に戻す

    return retn;
}

/* (主関数)pospの荷物は凍結しているか */
int freeze_check(int posp) {    // 返り値= 0:凍結してない  1:凍結している

    Fflag = 0;
    if (freeze_check_sub(posp,0) == 0) return 0;   // 縦方向へ移動可能か
    if (freeze_check_sub(posp,1) == 0) return 0;   // 横方向へ移動可能か
    return Fflag;
}
//*********************************************************
//* 局所探索(閉空間を形成している荷物だけのミニ探索)      *
//*********************************************************
byte taih_map[] = new byte[AREA];   // 本探索マップの退避
int  BQtop, BQend;                  // 局所探索用キューポインタ
int  Bkosu, Bsift, ALL_SP;
int  Btb[] = new int[K_MAX];

//----------------------------------------
// 局所荷物(閉空間を形成している荷物)抽出
//----------------------------------------
/* 閉空間位置poshを塗りつぶしながら再帰で波状に調べる */
int  get_packs_sub(int posh) {
    int posi, vect;

    work_map[posh]=1;
    for (vect=0; vect<4; vect++) {
        posi = posh + diff[vect];
        if (work_map[posi] == 0) {
            if (main_map[posi] == 0) {          // 空間の場合
                if (get_packs_sub(posi) == 1) return 1;
            } else if (main_map[posi] == 2) {   // 荷物の場合
                work_map[posi]=1;        // 2度抽出しないように
                Btb[Bkosu++] = posi;     // 荷物の位置を記録
                if (Bkosu == bbun+1) return 1;  // 多すぎ中止
            }
        }
    }
    return 0;
}
/* (主関数)poshに属する閉空間に隣接する荷物を抽出する */
int  get_packs(int posh) {
    int i;

    Bkosu=0;
    for (i=X_MAX+1; i<AREA-X_MAX-1; i++) work_map[i]=0; // 作業域初期化
    return get_packs_sub(posh);
}

//----------------------------------------
// ハッシュ(局所探索用)
//----------------------------------------
int Bhash_func(int post, int muk) {
    int  i, j, hash, retn;
    int data=0;

    /* データ圧縮 */
    for (i=j=0; j<Bkosu; i++)
        if (main_map[i] == 2) hstb[j++]=(byte)i;
    hstb[j++]=(byte)post;
    while (j <= kosu) hstb[j++]=0;

    /* 全ゴール */
    if (muk == 1) {
        for (i=0; i<Bkosu; i++)
            if (goal_map[hstb[i]] != 1) break;
        if (i == Bkosu) return 3;              // 3:全ゴールならOK
    } else {
        for (i=0; i<Bkosu; i++)
            if (pack_map[hstb[i]] != 1) break;
        if (i == Bkosu) return 5;              // 5:全ゴールならOK
    }

    /* ハッシュ値を求める */
    for (i=Bkosu; i>=0; i--)
        data = (data << Bsift) + hstb[i];
    if (data < 0) data *= -1;
    hash = (int)(data % B_SIZE);

    /* バケット内を探す */
    for (;;) {
        if (BACKET[hash][0] == 0) break;
        for (i=0; i<=kosu; i++)
            if (BACKET[hash][i] != hstb[i]) break;
        if (i > kosu) {
            if ((retn = OPTN[hash]) == 0) return 0; // 0:続行
            if ((retn>>2) == muk-1) return retn;    // 3,5:OK 4,6:NO
        }
        hash = (hash + R_HASH) % B_SIZE;
    }

    /* バケットに記録 */
    for (i=0; i<=kosu; i++)
        BACKET[hash][i]=hstb[i];
    QUEUE[BQend++]=hash;

    if (BQend-Qadd1>1000) return (muk==1)? 3: 5;    // 3,5:打切りOK

    return 0;                                       // 0:続行
}

//----------------------------------------
// 幅優先探索(局所探索用)
//----------------------------------------
int btb[] = new int[K_MAX];
int Bsearch(int all_space, int muk) {
    int i, adr, posp, posi, posj, pack, vect, post;

    while (BQtop < BQend) {
        adr=QUEUE[BQtop++];
        for (i=0; i<Bkosu; i++)
            main_map[btb[i]=BACKET[adr][i]]=2;
        active_zone(b1map,BACKET[adr][Bkosu]);

        for (pack=0; pack<Bkosu; pack++) {
            posp = btb[pack];                     // 荷物の位置
            for (vect=0; vect<4; vect++) {
                posi = posp + diff[vect];         // 荷物の手前
                if (b1map[posi] != 1) continue;
                if (muk == 1) {
                    posj = posp - diff[vect];     // 荷物の先
                    if (main_map[posj]==0 && dead_map[posj]==0) {
                        main_map[posj]=2;
                        main_map[posp]=0;
                        if (freeze_check(posj) == 0) {
                            post = active_zone(b2map,posp);
                            if (ac_cnt == all_space) return 3;       // 3:OK(閉空間で無くなった)
                            if (Bhash_func(post,muk) == 3) return 3; // 3:OK(全ゴールor過去の記録より)
                        }
                        main_map[posj]=0;
                        main_map[posp]=2;
                    }
                } else {
                    posj = posi + diff[vect];     // 荷物の前の前
                    if (main_map[posj] == 0) {
                        main_map[posp]=0;
                        main_map[posi]=2;
                        post = active_zone(b2map,posj);
                        if (ac_cnt == all_space) return 5;       // 5:OK(閉空間で無くなった)
                        if (Bhash_func(post,muk) == 5) return 5; // 5:OK(全ゴールor過去の記録より)
                        main_map[posp]=2;
                        main_map[posi]=0;
                    }
                }
            }
        }
        for (i=0; i<Bkosu; i++) main_map[btb[i]]=0;
    }
    return (muk == 1)? 4: 6;                                    // 4,6:NO(凍結する)
}

//----------------------------------------
// 局所探索主処理(0:凍結しない  1:凍結する)
//----------------------------------------
int check1(int posp, int posh, int muk) {
    int i, vect, posi=0, post, retn;

    /* pospの荷物が閉空間に接しているか？ */
    for (vect=0; vect<4; vect++) {
        posi = posp + diff[vect];
        if (main_map[posi]==0 && h2map[posi]==0) break;
    }
    if (vect == 4) return 0;

    if (muk == 1) {
        if (get_packs(posi) == 1) return 0; // 局所荷物を抽出(多すぎの場合中止)
    } else {
        if (get_packs(posh) == 1) return 0; // 局所荷物を抽出(多すぎの場合中止)
    }

    /* 本探索マップの退避と局所みにマップ作成 */
    for (i=X_MAX+1; i<AREA-X_MAX-1; i++) {
        taih_map[i]=main_map[i]; main_map[i]=wall_map[i];
    }
    for (i=0; i<Bkosu; i++) main_map[Btb[i]]=2;

    BQtop = BQend = Qadd1;
    Bsift = 24 / Bkosu;
    post = active_zone(b1map,posh);
    retn = Bhash_func(post,muk);    // 0でない場合は過去の記録より即決
                                    // 3:凍結しない  4:凍結する
    if (retn == 0) {

        /* 探索処理 */
        for (i=0; i<Bkosu; i++) main_map[Btb[i]]=0;
        retn = Bsearch(ALL_SP - Bkosu,muk);  // 引数=閉空間が解放された場合の空間面積

        /* 結果の書き込み */
        OPTN[QUEUE[Qadd1]]=(byte)retn;   // 3,5:OK  4,6:NO
        for (i=Qadd1+1; i<BQend; i++)    // 作業に使用したバケット消去
            BACKET[QUEUE[i]][0]=0;

        if ((++backetCnt)%5000 == 0) {    // 探索進行バー
            thinkBar++; drawBar(grf);
        }
    }

    /* 本探索マップ復元 */
    for (i=X_MAX+1; i<AREA-X_MAX-1; i++)
        main_map[i]=taih_map[i];

    return (retn==3 || retn==5)? 0: 1;
}

//*********************************************************
//* 本探索                                                *
//*********************************************************
//----------------------------------------
// ハッシュ法(本探索用)
//----------------------------------------
int hash_func(int post, int adr, int muk) {
    int  i, j, hash, data=0;

    /* 局面圧縮 */
    for (i=j=0; j<kosu; i++)
        if (main_map[i] == 2) hstb[j++]=(byte)i;
    hstb[kosu]=(byte)post;

    /* ハッシュ値を求める */
    for (i=kosu; i>=0; i--)
        data = (data << sift) + hstb[i];
    hash = data % B_SIZE;

    /* バケット内を探す */
    for (;;) {
        if (BACKET[hash][0] == 0) break;
        for (i=0; i<=kosu; i++)
            if (BACKET[hash][i] != hstb[i]) break;
        if (i > kosu) {
            if (OPTN[hash] == muk) return -1;  // 同形あり/探索続行
            chan=hash;  kara=adr;  return  0;  // 衝突地点発見
        }
        hash = (hash + R_HASH) % B_SIZE;
    }

    /* 新規パターン記録 */
    for (i=0; i<=kosu; i++)
        BACKET[hash][i]=hstb[i];
    LINK[hash]=adr;                     // リンク元
    OPTN[hash]=(byte)muk;               // 探索方向
    if (muk == 1) QUEUE[Qadd1++]=hash;
    else          QUEUE[Qadd2--]=hash;

    if ((++backetCnt)%5000 == 0) {      // 探索進行バー
        thinkBar++; drawBar(grf);
    }
    if (backetCnt >= Q_SIZE) return 4;  // 不足
    return -1;                          // 探索続行
}

//----------------------------------------
// 幅優先探索(本探索用)
//----------------------------------------
int postb[] = new int[K_MAX];

/* 通常探索 */
int search1() {
    int i, adr, posp, posi, posj, post, pack, vect;

    while (Qtop1 < Qend1) {
        adr=QUEUE[Qtop1++];
        for (i=0; i<kosu; i++)
            main_map[postb[i]=BACKET[adr][i]]=2;
        active_zone(h1map,BACKET[adr][kosu]);

        for (pack=0; pack<kosu; pack++) {
            posp = postb[pack];                   // 荷物の位置
            for (vect=0; vect<4; vect++) {
                posi = posp + diff[vect];         // 荷物の手前
                if (h1map[posi] != 1) continue;
                posj = posp - diff[vect];         // 荷物の先
                if (main_map[posj]==0 && dead_map[posj]==0) {
                    main_map[posj]=2;
                    main_map[posp]=0;
                    if (freeze_check(posj) == 0) {      // フリーズチェック
                        post = active_zone(h2map,posp);
                        if (check1(posj,posp,1) == 0)     // 局所探索
                            if ((i=hash_func(post,adr,1)) >= 0) return i;
                    }
                    main_map[posj]=0;
                    main_map[posp]=2;
                }
            }
        }
        for (i=0; i<kosu; i++) main_map[postb[i]]=0;
    }
    Qlen1 = Qadd1 - Qend1;
    Qtop1 = Qend1;
    Qend1 = Qadd1;
    if (Qlen1 == 0) return 3;    // 解が無かった
    return -1;                   // 探索続行
}

/* 逆解き探索 */
int search2() {
    int i, adr, posp, posi, posj, post, pack, vect;

    while (Qend2 < Qtop2) {
        adr=QUEUE[Qtop2--];
        for (i=0; i<kosu; i++)
            main_map[postb[i]=BACKET[adr][i]]=2;
        active_zone(h1map,BACKET[adr][kosu]);

        for (pack=0; pack<kosu; pack++) {
            posp = postb[pack];                  // 荷物の位置
            for (vect=0; vect<4; vect++) {
                posi = posp + diff[vect];        // 荷物の手前
                if (h1map[posi] != 1) continue;
                posj = posi + diff[vect];        // 荷物の前の前
                if (h1map[posj] == 1) {
                    main_map[posp]=0;
                    main_map[posi]=2;
                    post = active_zone(h2map,posj);
                    if (check1(posi,posj,2) == 0)     // 局所探索
                        if ((i=hash_func(post,adr,2)) >= 0) return i;
                    main_map[posp]=2;
                    main_map[posi]=0;
                }
            }
        }
        for (i=0; i<kosu; i++) main_map[postb[i]]=0;
    }
    Qlen2 = Qend2 - Qadd2;
    Qtop2 = Qend2;
    Qend2 = Qadd2;
    if (Qlen2 == 0) return 3;    // 解が無かった
    return -1;                   // 探索続行
}

//***************************************
//* 倉庫番を解く                        *
//***************************************
int puzzle() {
    int i, j, k, posh=0, retn;

    /* 編集マップ読み取り */
    for (i=j=k=kosu=0; i<AREA; i++) {
        switch (edit_map[i]) {
            case 0: wall_map[i]=0; goal_map[i]=0; pack_map[i]=0; main_map[i]=0;              break;
            case 1: wall_map[i]=0; goal_map[i]=1; pack_map[i]=0; main_map[i]=0;         k++; break;
            case 2: wall_map[i]=0; goal_map[i]=0; pack_map[i]=1; main_map[i]=2; kosu++;      break;
            case 3: wall_map[i]=0; goal_map[i]=1; pack_map[i]=1; main_map[i]=2; kosu++; k++; break;
            case 4: wall_map[i]=1; goal_map[i]=0; pack_map[i]=0; main_map[i]=1;              break;
            case 5: wall_map[i]=0; goal_map[i]=0; pack_map[i]=0; main_map[i]=0; posS=i; j++; break;
        }
    }
    if (k==0 || k!=kosu || j!=1) return 2;  // 2:マップが異常/
    if (kosu > K_MAX) return 1;             // 1:荷物が多すぎ/

    /* 作業領域初期化 */
    for (i=0; i<B_SIZE; i++) BACKET[i][0]=0;
    Qtop1 = Qend1 = Qadd1 = 0;
    Qtop2 = Qend2 = Qadd2 = Q_SIZE-1;
    backetCnt = 0;
    sift = 24 / kosu;
    bbun = kosu / 2;
    if (bbun < 2) bbun=0;
    if (bbun > 6) bbun=6;

    /* ダメを詰める(3方が壁に囲まれたゴールも無く人もいない空間をつぶす) */
    k=1;
    while (k == 1) {
        k=0;
        for (posh=0; posh<AREA; posh++) {
            if (main_map[posh]==0 && goal_map[posh]==0 && posh!=posS) {
                for (i=j=0; i<4; i++)
                    if (wall_map[posh+diff[i]]==1) j++;
                if (j > 2) { wall_map[posh]=main_map[posh]=1; k=1; }
            }
        }
    }

    /* 開始型登録 */
    posh = active_zone(h1map,posS);
    hash_func(posh,-1,1);
    for (i=0; i<AREA; i++)  main_map[i]=wall_map[i];
    Qlen1 = Qadd1 - Qend1;
    Qtop1 = Qend1;
    Qend1 = Qadd1;

    /* 完了型登録(人の位置により複数ある場合がある) */
    active_zone(h1map,posh);
    ALL_SP = ac_cnt;
    for (i=0; i<AREA; i++)
        if (goal_map[i] == 1) main_map[i]=2;
    for (i=0; i<AREA; i++) h2map[i]=0;
    for (i=0; i<AREA; i++) {
        if (main_map[i]==0 && h1map[i]==1 && h2map[i]==0) {
            active_zone(h2map,i);
            for (j=0; h2map[j]==0; j++);
            if (j == i)
                if (hash_func(i,-1,2) == 0) return 0; // 初めから完成
        }
    }
    for (i=0; i<AREA; i++)  main_map[i]=wall_map[i];
    Qlen2 = Qend2 - Qadd2;
    Qtop2 = Qend2;
    Qend2 = Qadd2;

    /* デッドゾーン調査 */
    dead_zone();

    /* 間口幅調整式逆解き挟みうち法 */
    do {
        if (Qlen1 < Qlen2) retn=search1();  // 通常探索
        else               retn=search2();  // 逆解き探索
    } while (retn == -1);
    return retn;
}

//***************************************
//* javaGUIと電子頭脳のインターフェース *
//***************************************
/* 2地点間の最短ルートを見つける為の歩数マップを作る */
void root(int pos1, byte step) {
    int pos2, vect;

    work_map[pos1]=step++;
    for (vect=0; vect<4; vect++) {
        pos2 = pos1 + diff[vect];
        if (main_map[pos2]==0 && work_map[pos2]>step)
            root(pos2,step);
    }
}
void computer() {
    int ret, next, prev, idx, adr, i, vect, step;
    int pos0, pos1=0, pos2=0, posh=0, posa, posb=0;

    thinkBar = push = 0;

    ret = puzzle();
    if (ret == 0) {
        /* リンクポインタを解答手順向きに統一する */
        if (OPTN[chan] == 1) {
            next=kara; adr=chan;
        } else {
            next=chan; adr=kara;
        }
        for ( ; adr>=0; adr=prev) {
            prev=LINK[adr];  LINK[adr]=next;  next=adr;
        }

        /* 解答アニメ用データを作る               */
        /*   QUEUE[]をアニメ用データに併用        */
        /*   main_map[]を荷を押す前の局面に使用   */
        /*   dead_map[]を荷を押した後の局面に併用 */
        adr=QUEUE[0];
        for (i=0; i<AREA; i++) main_map[i]=wall_map[i];
        for (i=0; i<kosu; i++) main_map[BACKET[adr][i]] = 2;
        posh = posS;    // 最初の人の位置
        idx=0;
        /* リンクポインタを辿る */
        for (adr=LINK[adr],tesu=0; adr>=0; adr=LINK[adr],tesu++) {
            for (i=0; i<AREA; i++) dead_map[i]=wall_map[i];
            for (i=0; i<kosu; i++) dead_map[BACKET[adr][i]] = 2;
            for (i=0; i<AREA; i++) {
                if (main_map[i]==2 && dead_map[i]==0) pos1=i; // 押す前の位置
                if (main_map[i]==0 && dead_map[i]==2) pos2=i; // 押した後の位置
                work_map[i] = (byte)AREA;
            }
            pos0 = pos1 - ( pos2 - pos1);                     // 押す前の人の位置
            root(pos0,(byte)1);                        // 歩数マップを作る
            work_map[pos1]=0;
            /* 歩数マップを見ながら最短ルートを歩く */
            for (posa=posh,step=work_map[posh]-1; step>=0; posa=posb,step--) {
                for (vect=0; vect<4; vect++) {
                    posb = posa + diff[vect];
                    if (work_map[posb] == step) break;
                }
                QUEUE[idx++] = posa*10000 + posb*10 + vect;   // 登録
            }

            /* 次の局面変化の為の準備 */
            for (i=0; i<AREA; i++)
                main_map[i]=dead_map[i];
            posh=pos1;
        }
        QUEUE[idx]=-1;           // 終端を(-1)で閉じる
        ansMsg=6;
    } else {
        ansMsg=ret;
    }
}
}