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;
}
}
}