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 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; posi0 && 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=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=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= 0) return i;
}
main_map[posj]=0;
main_map[posp]=2;
}
}
}
for (i=0; i= 0) return i;
main_map[posp]=2;
main_map[posi]=0;
}
}
}
for (i=0; i K_MAX) return 1; // 1:荷物が多すぎ/
/* 作業領域初期化 */
for (i=0; i 6) bbun=6;
/* ダメを詰める(3方が壁に囲まれたゴールも無く人もいない空間をつぶす) */
k=1;
while (k == 1) {
k=0;
for (posh=0; posh 2) { wall_map[posh]=main_map[posh]=1; k=1; }
}
}
}
/* 開始型登録 */
posh = active_zone(h1map,posS);
hash_func(posh,-1,1);
for (i=0; istep)
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=0; adr=LINK[adr],tesu++) {
for (i=0; i=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