Created
September 12, 2011 15:45
-
-
Save uwi/1211596 to your computer and use it in GitHub Desktop.
GDD2011 DevQuiz スライドパズル用
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.PrintWriter; | |
import java.util.Arrays; | |
import java.util.BitSet; | |
import java.util.Scanner; | |
/** | |
* 現在の解答状況と残りカウント数、残り問題等の表示 | |
* @author uwi | |
* | |
*/ | |
public class FCount { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static void solve() | |
{ | |
int lx = ni(), rx = ni(), ux = ni(), dx = ni(); | |
int[] x = {72187,81749,72303,81778}; | |
int n = ni(); | |
in.nextLine(); | |
int[] cts = new int[37]; | |
int ok = 0; | |
int[] cct = new int[4]; | |
int mx = 0; | |
BitSet lll = new BitSet(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String line2 = in2.nextLine(); | |
String[] sp = line.split(","); | |
int w = Integer.parseInt(sp[0]); | |
int h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
} | |
} | |
if(line2.length() == 0)cts[alive]++; | |
char[] str = line2.toCharArray(); | |
if(str.length > 0){ | |
ok++; | |
mx = Math.max(mx, str.length); | |
}else{ | |
tr(o); | |
tr(sp[2]); | |
for(int j = 0;j < h;j++){ | |
tr(sp[2].substring(w*j, w*(j+1))); | |
} | |
tr(); | |
} | |
if(str.length >= 120){ | |
tr(o, str.length); | |
tr(sp[2]); | |
for(int j = 0;j < h;j++){ | |
tr(sp[2].substring(w*j, w*(j+1))); | |
} | |
tr(); | |
} | |
for(char c : str){ | |
cct["LRUD".indexOf(c)]++; | |
} | |
} | |
int tot = 0; | |
for(int y : x)tot += y; | |
for(int y : cct)tot -= y; | |
tr("filled : " + ok); | |
tr("left : " + (5000-ok)); | |
tr("used parts : " + Arrays.toString(cct)); | |
tr("all parts : " + Arrays.toString(x)); | |
tr("remaining parts : " + tot); | |
tr("max length : " + mx); | |
tr("left surviver :"); | |
for(int i = 0;i < cts.length;i++){ | |
if(cts[i] > 0)tr(i, cts[i]); | |
} | |
tr(lll); | |
} | |
static int dec(char x) | |
{ | |
if(x == '=')return -1; | |
if(x >= '0' && x <= '9')return x - '0'; | |
return x - 'A' + 10; | |
} | |
public static void main(String[] args) throws Exception | |
{ | |
long s = System.currentTimeMillis(); | |
in = new Scanner(new File("x:\\input.txt")); | |
in2 = new Scanner(new File("x:\\output.txt")); | |
out = new PrintWriter(System.out); | |
solve(); | |
out.flush(); | |
tr(System.currentTimeMillis() - s+"ms"); | |
} | |
static int ni() { return Integer.parseInt(in.next()); } | |
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.PrintWriter; | |
import java.text.SimpleDateFormat; | |
import java.util.Arrays; | |
import java.util.Comparator; | |
import java.util.Date; | |
import java.util.HashMap; | |
import java.util.Iterator; | |
import java.util.Map; | |
import java.util.Random; | |
import java.util.Scanner; | |
import java.util.TreeSet; | |
/** | |
* 静的パターンIDDFS | |
* 20110901 | |
* @author uwi | |
* | |
*/ | |
public class FDFS4 { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static char[] udlr = "UDLR".toCharArray(); | |
static int[][] PT = new int[24][4]; // 隣接移動用の置換配列 | |
static int h, w; | |
static int[][][][][][][] ST; // 評価値計算用テーブル | |
static int[][] SETS; // 分割済集合の構成要素 | |
static Map<Long, Integer> dm; // 距離メモ | |
static char[] ret; // 現在の手順 | |
static String opt; // 最適手順 | |
static TreeSet<Datum> rank, nrank; // IDDFS用ランキング | |
static int L = 100000; // ランキングの最大要素数 | |
static Random gen = new Random(2011); | |
// 状態比較関数 | |
// 評価関数昇順, ハッシュ値昇順 | |
static Comparator<Datum> comp = new Comparator<Datum>(){ | |
public int compare(Datum a, Datum b){ | |
if(a.md - b.md != 0)return a.md - b.md; | |
return Long.signum(a.hash - b.hash); | |
}; | |
}; | |
static void solve() | |
{ | |
int p = 0; | |
int[] ord = new int[4]; | |
for(int i = 0;i < 4;i++)ord[i] = i; | |
do{ | |
PT[p++] = Arrays.copyOf(ord, 4); | |
}while(nextPermutation(ord)); | |
int lx = ni(), rx = ni(), ux = ni(), dx = ni(); | |
int n = ni(); | |
int ct = 0; | |
in.nextLine(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String[] sp = line.split(","); | |
w = Integer.parseInt(sp[0]); | |
h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
// 数値盤面作成 | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
int zr = 0, zc = 0; | |
long obs = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
if(b[j][k] == 0){ | |
zr = j; zc = k; | |
} | |
if(b[j][k] == -1){ | |
obs |= 1L<<j*w+k; | |
} | |
} | |
} | |
String line2 = in2.nextLine(); | |
int len = line2.length(); | |
int lim = len == 0 ? 150 : len; | |
if(o >= 0){ // 絞込み条件 | |
long S = System.currentTimeMillis(); | |
// テーブル作成 | |
makeDistTable(h, w, obs); | |
// 理想状態のハッシュ値を計算しておく | |
int[][] ideal = new int[h][w]; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
ideal[j][k] = b[j][k] == -1 ? -1 : j*w+k+1; | |
} | |
} | |
ideal[h-1][w-1] = 0; | |
long ei = enc(shrink(ideal)); | |
tr(o, h, w, sp[2], alive); | |
// 初期状態の作成 | |
long[] v = shrink(b); | |
dm = new HashMap<Long, Integer>(); | |
ret = new char[1000]; | |
opt = ""; | |
rank = new TreeSet<Datum>(comp); | |
rank.add(new Datum(v, new char[0], zr, zc)); | |
// IDDFS | |
for(int i = 0;i < lim && dm.size() < 8000000;i+=2){ | |
tr(i, dm.size(), rank.first().md, rank.last().md, L); | |
nrank = new TreeSet<Datum>(comp); | |
// 距離メモ大過去削除 | |
Iterator<Map.Entry<Long, Integer>> itr = dm.entrySet().iterator(); | |
while(itr.hasNext()){ | |
Map.Entry<Long, Integer> e = itr.next(); | |
if(e.getValue() < i-15){ | |
itr.remove(); | |
// dm.remove(e.getKey()); | |
} | |
} | |
// DFS | |
for(Datum da : rank){ | |
System.arraycopy(da.path, 0, ret, 0, da.path.length); | |
iddfsRoot(da.state, ei, da.zr, da.zc, i, h, w, i+2); | |
} | |
if(opt.length() > 0)break; | |
rank = nrank; | |
} | |
if(opt.length() > 0){ | |
// 解が存在した場合表示 | |
tr(opt.length(), opt, dm.size()); | |
out.println(opt); | |
out.flush(); | |
ct++; | |
}else{ | |
// 解が存在しない場合失敗 | |
tr("failed", dm.size()); | |
out.println(); | |
out.flush(); | |
} | |
long G = System.currentTimeMillis(); | |
tr(G-S+"ms"); | |
}else{ | |
out.println(); | |
} | |
} | |
tr(ct); | |
} | |
// 状態 | |
static class Datum | |
{ | |
public long[] state; // 盤面状態 | |
public char[] path; // 状態に至るまでの手順 | |
public int zr, zc; // 空白の位置 | |
public int md; // 評価関数 | |
public long hash; // ハッシュ値 | |
public Datum(long[] state, char[] path, int zr, int zc) { | |
this.state = state; | |
hash = enc(state); | |
md = dist(state, h, w, zr, zc); | |
this.path = path; | |
this.zr = zr; | |
this.zc = zc; | |
} | |
} | |
static void iddfsRoot(long[] v, long ei, int zr, int zc, int d, int h, int w, int dlim) | |
{ | |
for(int k : PT[gen.nextInt(24)]){ | |
int nr = zr + dr[k]; | |
int nc = zc + dc[k]; | |
int z; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && (z = getl(v, nr, nc, w)) != 63){ | |
ret[d] = udlr[k]; | |
writel(v, zr, zc, w, z); | |
writel(v, nr, nc, w, 62); | |
iddfs(v, ei, nr, nc, d+1, h, w, dlim); | |
writel(v, nr, nc, w, z); | |
writel(v, zr, zc, w, 62); | |
} | |
} | |
} | |
static void iddfs(long[] v, long ei, int zr, int zc, int d, int h, int w, int dlim) | |
{ | |
if(opt.length() > 0 && d >= opt.length())return; | |
long en = enc(v); | |
// cache check | |
Integer D = dm.get(en); | |
if(D != null && D <= d)return; | |
dm.put(en, d); | |
// 終了状態なら最適手順に登録 | |
if(en == ei){ | |
opt = new String(Arrays.copyOf(ret, d)); | |
// tr("found!", opt); | |
return; | |
} | |
// 指定手数に到達したら葉のデータをランキングに登録 | |
if(d == dlim){ | |
if(nrank.size() == L){ | |
if(comp.compare(new Datum(v, null, zr, zc), nrank.last()) < 0){ | |
nrank.add(new Datum(Arrays.copyOf(v, 4), Arrays.copyOf(ret, d), zr, zc)); | |
nrank.pollLast(); | |
} | |
}else{ | |
nrank.add(new Datum(Arrays.copyOf(v, 4), Arrays.copyOf(ret, d), zr, zc)); | |
} | |
return; | |
} | |
// 隣接移動 | |
for(int k : PT[gen.nextInt(24)]){ | |
int nr = zr + dr[k]; | |
int nc = zc + dc[k]; | |
int z; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && (z = getl(v, nr, nc, w)) != 63){ | |
ret[d] = udlr[k]; | |
writel(v, zr, zc, w, z); | |
writel(v, nr, nc, w, 62); | |
iddfs(v, ei, nr, nc, d+1, h, w, dlim); | |
writel(v, nr, nc, w, z); | |
writel(v, zr, zc, w, 62); | |
} | |
} | |
} | |
// 状態から特定の座標のセルの値を取り出す | |
static int getl(long[] v, int r, int c, int m) | |
{ | |
int u = r*m+c; | |
return (int)(v[u/10]>>>(u%10*6))&63; | |
} | |
// 状態の特定の座標のセルの値を書き換える | |
static void writel(long[] v, int r, int c, int m, long z) | |
{ | |
int u = r*m+c; | |
v[u/10] &= ~(63L<<(u%10*6)); | |
v[u/10] |= z<<(u%10*6); | |
} | |
static int[] dr = {-1,1,0,0}; | |
static int[] dc = {0,0,-1,1}; | |
// 評価値計算用テーブル作成 | |
static void makeDistTable(int h, int w, long obs) | |
{ | |
tr("split start"); | |
// (hw)^x<=LIM | |
// x<=logLIM/log hw | |
int x = (int)(Math.log(20000000)/Math.log(h*w)); | |
x = 4; | |
int div = (h*w - Long.bitCount(obs) - 1 + x - 1) / x; | |
long[] sp = split(h, w, obs|1L<<h*w-1, div); | |
tr("split end"); | |
tr("make start"); | |
ST = new int[div][][][][][][]; | |
SETS = new int[div][]; | |
for(int i = 0;i < div;i++){ | |
int bc = Long.bitCount(sp[i]); | |
if(bc == 3){ | |
ST[i] = new int[][][][][][]{{{simulate3(h, w, obs, sp[i])}}}; | |
}else if(bc == 4){ | |
ST[i] = new int[][][][][][]{{simulate4(h, w, obs, sp[i])}}; | |
} | |
int[] o = new int[bc]; | |
long t = sp[i]; | |
for(int j = 0;j < bc;j++,t&=t-1){ | |
o[j] = Long.numberOfTrailingZeros(t); | |
} | |
SETS[i] = o; | |
} | |
tr("make end"); | |
} | |
// 要素数3の集合についてテーブルを作成 | |
static int[][][] simulate3(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[3]; | |
for(int i = 0;i < 3;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int hw = h*w; | |
int[][][] d = new int[hw][hw][hw]; | |
for(int i = 0;i < hw;i++){ | |
for(int j = 0;j < hw;j++){ | |
Arrays.fill(d[i][j], 99999); | |
} | |
} | |
int[][] q = new int[hw*hw*hw][]; | |
q[0] = o; | |
d[o[0]][o[1]][o[2]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 3;l++){ | |
o1: | |
for(int k = 0;k < 4;k++){ | |
int nr = cur[l]/w + dr[k]; | |
int nc = cur[l]%w + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
for(int m = 0;m < 3;m++){ | |
if(nr*w+nc == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 3); | |
no[l] = nr*w+nc; | |
if(d[no[0]][no[1]][no[2]] == 99999){ | |
d[no[0]][no[1]][no[2]] = d[cur[0]][cur[1]][cur[2]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数4の集合についてテーブルを作成 | |
static int[][][][] simulate4(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[4]; | |
for(int i = 0;i < 4;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int hw = h*w; | |
int[][][][] d = new int[hw][hw][hw][hw]; | |
for(int i = 0;i < hw;i++){ | |
for(int j = 0;j < hw;j++){ | |
for(int k = 0;k < hw;k++){ | |
Arrays.fill(d[i][j][k], 99999); | |
} | |
} | |
} | |
int[][] q = new int[hw*hw*hw*hw][]; | |
q[0] = o; | |
d[o[0]][o[1]][o[2]][o[3]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 4;l++){ | |
o1: | |
for(int k = 0;k < 4;k++){ | |
int nr = cur[l]/w + dr[k]; | |
int nc = cur[l]%w + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
for(int m = 0;m < 4;m++){ | |
if(nr*w+nc == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 4); | |
no[l] = nr*w+nc; | |
if(d[no[0]][no[1]][no[2]][no[3]] == 99999){ | |
d[no[0]][no[1]][no[2]][no[3]] = d[cur[0]][cur[1]][cur[2]][cur[3]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 盤面の最適分割を乱択で計算 | |
static long[] split(int N, int M, long obs, int D) | |
{ | |
long[] opt = new long[D]; | |
Random gen = new Random(); | |
int left = N*M-Long.bitCount(obs) - D; | |
long mask = (1L<<N*M)-1; | |
long lmask = 0; | |
long rmask = 0; | |
for(int i = 0;i < N;i++){ | |
lmask |= 1L<<i*M; | |
rmask |= 1L<<i*M+M-1; | |
} | |
lmask = ~lmask; | |
rmask = ~rmask; | |
long S = System.currentTimeMillis(); | |
int maxconn = 0; | |
outer: | |
for(int o = 0;o < 100000;o++){ | |
long[] b = new long[D]; | |
long all = obs; | |
for(int i = 0;i < D;i++){ | |
int pos = -1; | |
do{ | |
pos = gen.nextInt(N*M); | |
}while(all<<63-pos<0); | |
b[i] |= 1L<<pos; | |
all |= 1L<<pos; | |
} | |
for(int i = 0;i < left;i++){ | |
int c = i % D; | |
long nei = (b[c]<<M|b[c]>>M|(b[c]&lmask)>>1|(b[c]&rmask)<<1)&~all&mask; | |
if(nei == 0)continue outer; | |
int q = gen.nextInt(Long.bitCount(nei)); | |
for(int j = 1;j <= q;j++, nei&=nei-1); | |
long chosen = nei&-nei; | |
b[c] |= chosen; | |
all |= chosen; | |
} | |
int conn = 0; | |
for(int i = 0;i < D;i++){ | |
conn += Long.bitCount((b[i]<<M)&b[i]); | |
conn += Long.bitCount((b[i]>>M)&b[i]); | |
conn += Long.bitCount(((b[i]&lmask)>>1)&b[i]); | |
conn += Long.bitCount(((b[i]&rmask)<<1)&b[i]); | |
} | |
if(conn > maxconn){ | |
maxconn = conn; | |
opt = Arrays.copyOf(b, D); | |
} | |
} | |
long G = System.currentTimeMillis(); | |
char[][] U = new char[N][M]; | |
for(int i = 0;i < N;i++){ | |
for(int j = 0;j < M;j++){ | |
int q = i*M+j; | |
if(obs<<63-q<0){ | |
U[i][j] = '#'; | |
continue; | |
} | |
for(int k = 0;k < D;k++){ | |
if(opt[k]<<63-q<0){ | |
U[i][j] = (char)('A'+k); | |
break; | |
} | |
} | |
} | |
} | |
for(char[] row : U){ | |
tr(row); | |
} | |
tr(G-S+"ms"); | |
return opt; | |
} | |
// 評価値計算 | |
static int dist(long[] v, int h, int w, int zr, int zc) | |
{ | |
int ret = 0; | |
int[] ipos = new int[h*w]; | |
int hw = h*w; | |
int p = 0; | |
for(int i = 0;i < 4;i++){ | |
for(int j = 0;j < 60;j += 6, p++){ | |
if(p >= hw)break; | |
int e = (int)(v[i]>>>j)&63; | |
if(e < 62)ipos[e-1] = p; | |
} | |
} | |
for(int i = 0;i < SETS.length;i++){ | |
int l = SETS[i].length; | |
int[] x = new int[6]; | |
for(int j = 0;j < l;j++){ | |
x[6-l+j] = ipos[SETS[i][j]]; | |
} | |
ret += ST[i][x[0]][x[1]][x[2]][x[3]][x[4]][x[5]]; | |
} | |
return ret; | |
} | |
// 盤面情報の圧縮 | |
static long[] shrink(int[][] b) | |
{ | |
long[] ret = new long[4]; | |
int h = b.length; | |
int w = b[0].length; | |
int p = 0; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int v = b[i][j]; | |
if(v == 0)v = 62; | |
if(v == -1)v = 63; | |
ret[p/10] |= ((long)v) << (p%10*6); | |
p++; | |
} | |
} | |
return ret; | |
} | |
// 展開 | |
// static int[][] expand(long[] v, int h, int w) | |
// { | |
// int[][] ret = new int[h][w]; | |
// int p = 0; | |
// for(int i = 0;i < 4;i++){ | |
// for(int j = 0;j < 60;j += 6){ | |
// if(p >= h*w)break; | |
// int e = (int)(v[i]>>>j)&63; | |
// if(e == 63)e = -1; | |
// if(e == 62)e = 0; | |
// ret[p/w][p%w] = e; | |
// p++; | |
// } | |
// } | |
// return ret; | |
// } | |
// ハッシュ値計算 | |
static long enc(long[] u) | |
{ | |
return (((u[3]+(u[3]>>>32))*37+(u[2]+(u[2]>>>32)))*37+(u[1]+(u[1]>>>32)))*37+(u[0]+(u[0]>>>32)); | |
} | |
// 入力文字を数値に変換 | |
static int dec(char x) | |
{ | |
if(x == '=')return -1; | |
if(x >= '0' && x <= '9')return x - '0'; | |
return x - 'A' + 10; | |
} | |
static boolean nextPermutation(int[] src) | |
{ | |
int i; | |
for(i = src.length - 2;i >= 0 && src[i] > src[i+1];i--); | |
if(i == -1)return false; | |
int j; | |
for(j = i + 1;j < src.length && src[i] < src[j];j++); | |
int d = src[i]; src[i] = src[j - 1]; src[j - 1] = d; | |
for(int p = i + 1, q = src.length - 1;p < q;p++,q--){ | |
d = src[p]; src[p] = src[q]; src[q] = d; | |
} | |
return true; | |
} | |
public static void main(String[] args) throws Exception | |
{ | |
long s = System.currentTimeMillis(); | |
in = INPUT.isEmpty() ? new Scanner(new File("x:\\input.txt")) : new Scanner(INPUT); | |
in2 = new Scanner(new File("x:\\output.txt")); | |
out = new PrintWriter("x:\\output" + (new SimpleDateFormat("MMddHHmm")).format(new Date()) + ".txt"); | |
// out = new PrintWriter(System.out); | |
solve(); | |
out.flush(); | |
tr(System.currentTimeMillis() - s+"ms"); | |
} | |
static int ni() { return Integer.parseInt(in.next()); } | |
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.PrintWriter; | |
import java.text.SimpleDateFormat; | |
import java.util.ArrayDeque; | |
import java.util.Arrays; | |
import java.util.Date; | |
import java.util.HashMap; | |
import java.util.Map; | |
import java.util.Queue; | |
import java.util.Random; | |
import java.util.Scanner; | |
/** | |
* 静的パターンえせMCMC | |
* 20110902 | |
* @author uwi | |
* | |
*/ | |
public class FDFS4MCMC { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static char[] udlr = "UDLR".toCharArray(); | |
static int[][][][][][][] ST; // 評価値計算用テーブル | |
static int[][] SETS; // 分割済集合の構成要素 | |
static int[] SMAP; // シェイクシェイクブギーな胸騒ぎ | |
static int SP; | |
static Random gen = new Random(2011); | |
static void solve() | |
{ | |
int lx = ni(), rx = ni(), ux = ni(), dx = ni(); | |
int n = ni(); | |
int ct = 0; | |
in.nextLine(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String[] sp = line.split(","); | |
int w = Integer.parseInt(sp[0]); | |
int h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
// 数値盤面作成 | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
int zr = 0, zc = 0; | |
long obs = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
if(b[j][k] == 0){ | |
zr = j; zc = k; | |
} | |
if(b[j][k] == -1){ | |
obs |= 1L<<j*w+k; | |
} | |
} | |
} | |
String line2 = in2.nextLine(); | |
int len = line2.length(); | |
len = 0; | |
int lim = len == 0 ? 25000 : len; | |
if(o >= 0){ // 絞込み条件 | |
long S = System.currentTimeMillis(); | |
tr(o, h, w, sp[2], alive); | |
// テーブル作成 | |
makeDistTable(h, w, obs); | |
// 理想状態のハッシュ値を計算しておく | |
int[][] ideal = new int[h][w]; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
ideal[j][k] = b[j][k] == -1 ? -1 : j*w+k+1; | |
} | |
} | |
ideal[h-1][w-1] = 0; | |
long ei = enc(shrink(ideal)); | |
// 初期状態の作成 | |
long[] ov = shrink(b); | |
Map<Long, Integer> dm = new HashMap<Long, Integer>(); | |
char[] ret = new char[30000]; | |
String opt = ""; | |
int optlen = 99999; | |
int ozr = zr, ozc = zc; | |
int[][][][] neis = new int[h][w][][]; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int B = 0; | |
for(int k = 0;k < 4;k++){ | |
int nr = i + dr[k]; | |
int nc = j + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
B |= 1<<k; | |
} | |
} | |
neis[i][j] = new int[Integer.bitCount(B)][3]; | |
int c = 0; | |
for(int k = 0;k <= 3;k++){ | |
if(B<<31-k<0){ | |
neis[i][j][c][0] = i + dr[k]; | |
neis[i][j][c][1] = j + dc[k]; | |
neis[i][j][c][2] = udlr[k]; | |
c++; | |
} | |
} | |
} | |
} | |
double[] E = new double[1000]; | |
for(int j = 0;j < 1000;j++){ | |
E[j] = Math.exp(-(double)j); | |
} | |
int od = dist(ov, h, w, zr, zc); | |
for(int j = 0;j < 5000;j++){ | |
if(j % 10 == 0 || optlen == 99999)tr(j, optlen); | |
long[] v = Arrays.copyOf(ov, 4); | |
int d = 0; | |
int prevd = od; | |
zr = ozr; zc = ozc; | |
for(int i = 0;d < lim && d < optlen && i < 2000000;i++){ | |
// if(i % 10000 == 0)tr(i, d, prevd); | |
// // 距離メモ大過去削除 | |
// Iterator<Map.Entry<Long, Integer>> itr = dm.entrySet().iterator(); | |
// while(itr.hasNext()){ | |
// Map.Entry<Long, Integer> e = itr.next(); | |
// if(e.getValue() < i-13){ | |
// itr.remove(); | |
//// dm.remove(e.getKey()); | |
// } | |
// } | |
int k = gen.nextInt(neis[zr][zc].length); | |
int nr = neis[zr][zc][k][0]; | |
int nc = neis[zr][zc][k][1]; | |
int z = getl(v, nr, nc, w); | |
writel(v, zr, zc, w, z); | |
writel(v, nr, nc, w, 62); | |
long en = enc(v); | |
// 終了状態なら最適手順に登録 | |
if(en == ei){ | |
ret[d++] = (char)neis[zr][zc][k][2]; | |
opt = new String(Arrays.copyOf(ret, d)); | |
optlen = d; | |
tr("found!", opt); | |
break; | |
} | |
int curd = dist(v, h, w, nr, nc); | |
if(curd < prevd || gen.nextDouble() < E[curd-prevd]){ | |
prevd = curd; | |
ret[d++] = (char)neis[zr][zc][k][2]; | |
zr = nr; | |
zc = nc; | |
}else{ | |
writel(v, nr, nc, w, z); | |
writel(v, zr, zc, w, 62); | |
} | |
} | |
// tr(prevd); | |
} | |
if(opt.length() > 0){ | |
while(true){ | |
int oo = opt.length(); | |
opt = opt.replace("LR", ""); | |
opt = opt.replace("RL", ""); | |
opt = opt.replace("UD", ""); | |
opt = opt.replace("DU", ""); | |
if(oo == opt.length())break; | |
} | |
// 解が存在した場合表示 | |
tr(opt.length(), opt, dm.size()); | |
out.println(opt); | |
out.flush(); | |
ct++; | |
}else{ | |
// 解が存在しない場合失敗 | |
tr("failed", dm.size()); | |
out.println(); | |
out.flush(); | |
} | |
long G = System.currentTimeMillis(); | |
tr(G-S+"ms"); | |
}else{ | |
out.println(); | |
} | |
} | |
tr(ct); | |
} | |
// 状態から特定の座標のセルの値を取り出す | |
static int getl(long[] v, int r, int c, int m) | |
{ | |
int u = r*m+c; | |
return (int)(v[u/10]>>>(u%10*6))&63; | |
} | |
// 状態の特定の座標のセルの値を書き換える | |
static void writel(long[] v, int r, int c, int m, long z) | |
{ | |
int u = r*m+c; | |
v[u/10] &= ~(63L<<(u%10*6)); | |
v[u/10] |= z<<(u%10*6); | |
} | |
static int[] dr = {-1,1,0,0}; | |
static int[] dc = {0,0,-1,1}; | |
// 評価値計算用テーブル作成 | |
static void makeDistTable(int h, int w, long obs) | |
{ | |
tr("split begin"); | |
// (hw)^x<=LIM | |
// x<=logLIM/log hw | |
int x = (int)(Math.log(20000000)/Math.log(h*w)); | |
x = 5; | |
int div = (h*w - Long.bitCount(obs) - 1 + x - 1) / x; | |
long[] sp = split(h, w, obs|1L<<h*w-1, div); | |
tr("split end"); | |
tr("make begin"); | |
int hw = h*w; | |
SMAP = new int[hw]; | |
SP = 0; | |
for(int i = 0;i < h*w;i++){ | |
if(obs<<63-i>=0){ | |
SMAP[i] = SP++; | |
} | |
} | |
ST = new int[div][][][][][][]; | |
SETS = new int[div][]; | |
for(int i = 0;i < div;i++){ | |
int bc = Long.bitCount(sp[i]); | |
tr(i, bc); | |
if(bc == 3){ | |
ST[i] = new int[][][][][][]{{{simulate3(h, w, obs, sp[i])}}}; | |
}else if(bc == 4){ | |
ST[i] = new int[][][][][][]{{simulate4(h, w, obs, sp[i])}}; | |
}else if(bc == 5){ | |
ST[i] = new int[][][][][][]{simulate5(h, w, obs, sp[i])}; | |
} | |
int[] o = new int[bc]; | |
long t = sp[i]; | |
for(int j = 0;j < bc;j++,t&=t-1){ | |
o[j] = Long.numberOfTrailingZeros(t); | |
} | |
SETS[i] = o; | |
} | |
tr("make end"); | |
} | |
// 要素数3の集合についてテーブルを作成 | |
static int[][][] simulate3(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[3]; | |
for(int i = 0;i < 3;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int hw = h*w; | |
int[][][] d = new int[SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
Arrays.fill(d[i][j], 99999); | |
} | |
} | |
int[][] q = new int[SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 3;l++){ | |
o1: | |
for(int k = 0;k < 4;k++){ | |
int nr = cur[l]/w + dr[k]; | |
int nc = cur[l]%w + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
for(int m = 0;m < 3;m++){ | |
if(nr*w+nc == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 3); | |
no[l] = nr*w+nc; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数4の集合についてテーブルを作成 | |
static int[][][][] simulate4(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[4]; | |
for(int i = 0;i < 4;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int hw = h*w; | |
int[][][][] d = new int[SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
Arrays.fill(d[i][j][k], 99999); | |
} | |
} | |
} | |
int[][] q = new int[SP*SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 4;l++){ | |
o1: | |
for(int k = 0;k < 4;k++){ | |
int nr = cur[l]/w + dr[k]; | |
int nc = cur[l]%w + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
for(int m = 0;m < 4;m++){ | |
if(nr*w+nc == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 4); | |
no[l] = nr*w+nc; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]][SMAP[cur[3]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数5の集合についてテーブルを作成 | |
static int[][][][][] simulate5(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[5]; | |
int oc = 0; | |
for(int i = 0;i < 5;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
oc |= o[i]<<(6*i); | |
} | |
int[][][][][] d = new int[SP][SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
for(int l = 0;l < SP;l++){ | |
Arrays.fill(d[i][j][k][l], 99999); | |
} | |
} | |
} | |
} | |
Queue<Integer> q = new ArrayDeque<Integer>(); | |
// int[] q = new int[SP*SP*SP*SP*SP]; | |
q.add(oc); | |
// q[0] = oc; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]][SMAP[o[4]]] = 0; | |
// int r = 1; | |
// for(int p = 0;p < r;p++){ | |
while(!q.isEmpty()){ | |
int cur = q.poll(); | |
int[] curo = new int[5]; | |
for(int i = 0;i < 5;i++){ | |
curo[i] = cur>>6*i&63; | |
} | |
int curd = d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]]; | |
for(int l = 0;l < 5;l++){ | |
int nya = curo[l]; | |
o1: | |
for(int k = 0;k < 4;k++){ | |
int nr = nya/w + dr[k]; | |
int nc = nya%w + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
for(int m = 0;m < 5;m++){ | |
if(nr*w+nc == curo[m]){ | |
continue o1; | |
} | |
} | |
curo[l] = nr*w+nc; | |
if(d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] == 99999){ | |
d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] = curd + 1; | |
int code = 0; | |
for(int i = 0;i < 5;i++){ | |
code |= curo[i]<<(6*i); | |
} | |
q.add(code); | |
// q[r++] = code; | |
} | |
} | |
} | |
curo[l] = nya; | |
} | |
} | |
return d; | |
} | |
// 盤面の最適分割を乱択で計算 | |
static long[] split(int N, int M, long obs, int D) | |
{ | |
long[] opt = new long[D]; | |
int left = N*M-Long.bitCount(obs) - D; | |
long mask = (1L<<N*M)-1; | |
long lmask = 0; | |
long rmask = 0; | |
for(int i = 0;i < N;i++){ | |
lmask |= 1L<<i*M; | |
rmask |= 1L<<i*M+M-1; | |
} | |
lmask = ~lmask; | |
rmask = ~rmask; | |
long S = System.currentTimeMillis(); | |
int maxconn = 0; | |
outer: | |
for(int o = 0;o < 100000;o++){ | |
long[] b = new long[D]; | |
long all = obs; | |
for(int i = 0;i < D;i++){ | |
int pos = -1; | |
do{ | |
pos = gen.nextInt(N*M); | |
}while(all<<63-pos<0); | |
b[i] |= 1L<<pos; | |
all |= 1L<<pos; | |
} | |
for(int i = 0;i < left;i++){ | |
int c = i % D; | |
long nei = (b[c]<<M|b[c]>>M|(b[c]&lmask)>>1|(b[c]&rmask)<<1)&~all&mask; | |
if(nei == 0)continue outer; | |
int q = gen.nextInt(Long.bitCount(nei)); | |
for(int j = 1;j <= q;j++, nei&=nei-1); | |
long chosen = nei&-nei; | |
b[c] |= chosen; | |
all |= chosen; | |
} | |
int conn = 0; | |
for(int i = 0;i < D;i++){ | |
conn += Long.bitCount((b[i]<<M)&b[i]); | |
conn += Long.bitCount((b[i]>>M)&b[i]); | |
conn += Long.bitCount(((b[i]&lmask)>>1)&b[i]); | |
conn += Long.bitCount(((b[i]&rmask)<<1)&b[i]); | |
} | |
if(conn > maxconn){ | |
maxconn = conn; | |
opt = Arrays.copyOf(b, D); | |
} | |
} | |
long G = System.currentTimeMillis(); | |
char[][] U = new char[N][M]; | |
for(int i = 0;i < N;i++){ | |
for(int j = 0;j < M;j++){ | |
int q = i*M+j; | |
if(obs<<63-q<0){ | |
U[i][j] = '#'; | |
continue; | |
} | |
for(int k = 0;k < D;k++){ | |
if(opt[k]<<63-q<0){ | |
U[i][j] = (char)('A'+k); | |
break; | |
} | |
} | |
} | |
} | |
for(char[] row : U){ | |
tr(row); | |
} | |
tr(G-S+"ms"); | |
return opt; | |
} | |
// 評価値計算 | |
static int dist(long[] v, int h, int w, int zr, int zc) | |
{ | |
int ret = 0; | |
int[] ipos = new int[h*w]; | |
int hw = h*w; | |
int p = 0; | |
for(int i = 0;i < 4;i++){ | |
for(int j = 0;j < 60;j += 6, p++){ | |
if(p >= hw)break; | |
int e = (int)(v[i]>>>j)&63; | |
if(e < 62)ipos[e-1] = p; | |
} | |
} | |
for(int i = 0;i < SETS.length;i++){ | |
int l = SETS[i].length; | |
int[] x = new int[6]; | |
for(int j = 0;j < l;j++){ | |
x[6-l+j] = ipos[SETS[i][j]]; | |
} | |
ret += ST[i][SMAP[x[0]]][SMAP[x[1]]][SMAP[x[2]]][SMAP[x[3]]][SMAP[x[4]]][SMAP[x[5]]]; | |
} | |
return ret; | |
} | |
// 盤面情報の圧縮 | |
static long[] shrink(int[][] b) | |
{ | |
long[] ret = new long[4]; | |
int h = b.length; | |
int w = b[0].length; | |
int p = 0; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int v = b[i][j]; | |
if(v == 0)v = 62; | |
if(v == -1)v = 63; | |
ret[p/10] |= ((long)v) << (p%10*6); | |
p++; | |
} | |
} | |
return ret; | |
} | |
// 展開 | |
// static int[][] expand(long[] v, int h, int w) | |
// { | |
// int[][] ret = new int[h][w]; | |
// int p = 0; | |
// for(int i = 0;i < 4;i++){ | |
// for(int j = 0;j < 60;j += 6){ | |
// if(p >= h*w)break; | |
// int e = (int)(v[i]>>>j)&63; | |
// if(e == 63)e = -1; | |
// if(e == 62)e = 0; | |
// ret[p/w][p%w] = e; | |
// p++; | |
// } | |
// } | |
// return ret; | |
// } | |
// ハッシュ値計算 | |
static long enc(long[] u) | |
{ | |
return (((u[3]+(u[3]>>>32))*37+(u[2]+(u[2]>>>32)))*37+(u[1]+(u[1]>>>32)))*37+(u[0]+(u[0]>>>32)); | |
} | |
// 入力文字を数値に変換 | |
static int dec(char x) | |
{ | |
if(x == '=')return -1; | |
if(x >= '0' && x <= '9')return x - '0'; | |
return x - 'A' + 10; | |
} | |
static boolean nextPermutation(int[] src) | |
{ | |
int i; | |
for(i = src.length - 2;i >= 0 && src[i] > src[i+1];i--); | |
if(i == -1)return false; | |
int j; | |
for(j = i + 1;j < src.length && src[i] < src[j];j++); | |
int d = src[i]; src[i] = src[j - 1]; src[j - 1] = d; | |
for(int p = i + 1, q = src.length - 1;p < q;p++,q--){ | |
d = src[p]; src[p] = src[q]; src[q] = d; | |
} | |
return true; | |
} | |
public static void main(String[] args) throws Exception | |
{ | |
long s = System.currentTimeMillis(); | |
in = INPUT.isEmpty() ? new Scanner(new File("x:\\input.txt")) : new Scanner(INPUT); | |
in2 = new Scanner(new File("x:\\output.txt")); | |
out = new PrintWriter("x:\\output" + (new SimpleDateFormat("MMddHHmm")).format(new Date()) + ".txt"); | |
// out = new PrintWriter(System.out); | |
solve(); | |
out.flush(); | |
tr(System.currentTimeMillis() - s+"ms"); | |
} | |
static int ni() { return Integer.parseInt(in.next()); } | |
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.PrintWriter; | |
import java.text.SimpleDateFormat; | |
import java.util.ArrayDeque; | |
import java.util.Arrays; | |
import java.util.BitSet; | |
import java.util.Comparator; | |
import java.util.Date; | |
import java.util.Iterator; | |
import java.util.LinkedHashMap; | |
import java.util.Map; | |
import java.util.Queue; | |
import java.util.Random; | |
import java.util.Scanner; | |
import java.util.TreeSet; | |
/** | |
* IDA*のようなもの | |
* 20110912 | |
* @author uwi | |
* | |
*/ | |
public class FIDA { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static char[] udlr = "UDLR".toCharArray(); | |
static int[][][][][][][] ST; // 評価値計算用テーブル | |
static int[][] SETS; // 分割済集合の構成要素 | |
static int[] SMAP; // シェイクシェイクブギーな胸騒ぎ | |
static int SP; // STの単位=壁以外のセルの個数 | |
static int IDLIM = 2000000; // キューの最大要素数 | |
static int MEMOLIM = 4000000; // メモの最大状態数 | |
static Random gen = new Random(20119); | |
static int[][][] NEIS; // 隣接移動情報格納用 | |
// 状態比較関数 | |
// 距離+評価関数昇順, 評価関数昇順, ハッシュ値昇順 | |
static Comparator<Datum> comp = new Comparator<Datum>(){ | |
public int compare(Datum a, Datum b){ | |
int sub = (3*a.d + a.md) - (3*b.d + b.md); // WA* | |
if(sub != 0)return sub; | |
if(a.md - b.md != 0)return a.md - b.md; | |
return Long.signum(a.hash - b.hash); | |
}; | |
}; | |
static void solve() | |
{ | |
ni(); ni(); ni(); ni(); | |
int n = ni(); | |
int ct = 0; | |
in.nextLine(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String[] sp = line.split(","); | |
int w = Integer.parseInt(sp[0]); | |
int h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
// 数値盤面作成 | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
int ozr = 0, ozc = 0; | |
long obs = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
if(b[j][k] == 0){ | |
ozr = j; ozc = k; | |
} | |
if(b[j][k] == -1){ | |
obs |= 1L<<j*w+k; | |
} | |
} | |
} | |
// 探索手数上限を設定 | |
String line2; | |
int len; | |
if(in2 != null){ | |
line2 = in2.nextLine(); | |
len = line2.length(); | |
}else{ | |
line2 = ""; | |
len = 0; | |
} | |
int lim = len == 0 ? 190 : len; | |
if(len>=0){ // 絞り込み条件 | |
long S = System.currentTimeMillis(); | |
tr(o, h, w, sp[2], alive, lim); | |
// 隣接移動キャッシュ作成 | |
NEIS = new int[h*w][][]; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int B = 0; | |
for(int k = 0;k < 4;k++){ | |
int nr = i + dr[k]; | |
int nc = j + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
B |= 1<<k; | |
} | |
} | |
NEIS[i*w+j] = new int[Integer.bitCount(B)][2]; | |
int c = 0; | |
for(int k = 0;k <= 3;k++){ | |
if(B<<31-k<0){ | |
NEIS[i*w+j][c][0] = (i+dr[k])*w + (j+dc[k]); | |
NEIS[i*w+j][c][1] = k; | |
c++; | |
} | |
} | |
} | |
} | |
// 評価値テーブル作成 | |
if(!makeDistTable(h, w, obs)){ | |
tr("failed to make distTable!"); | |
out.println(); | |
out.flush(); | |
continue; | |
} | |
// 理想状態のハッシュ値を計算しておく | |
int[][] ideal = new int[h][w]; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
ideal[j][k] = b[j][k] == -1 ? -1 : j*w+k+1; | |
} | |
} | |
ideal[h-1][w-1] = 0; | |
long ei = enc(shrink(ideal)); | |
// 初期状態の作成 | |
Map<Long, Integer> dm = new LinkedHashMap<Long, Integer>(); | |
String opt = ""; | |
TreeSet<Datum> q = new TreeSet<Datum>(comp); | |
q.add(new Datum(shrink(b), new BitSet(), ozr*w+ozc, 0, h, w)); | |
Runtime rt = Runtime.getRuntime(); | |
int step = 0; | |
while(!q.isEmpty()){ | |
Datum cur = q.pollFirst(); | |
if(++step % 20000 == 0){ | |
// ステップ数, キューのサイズ, 現在探索中のパスの長さ, 現在探索中のノードの評価値, 距離キャッシュのサイズ, 使用中のメモリ, 探索上限 | |
tr(step, q.size(), cur.d, cur.md, dm.size(), rt.totalMemory() - rt.freeMemory(), lim); | |
} | |
long[] v = cur.state; | |
int z = cur.z; | |
// cache check | |
int d = cur.d; | |
if(d >= lim)continue; | |
// 終了状態なら最適手順に登録 | |
if(cur.hash == ei && (opt.length() == 0 || d < opt.length())){ | |
opt = expandPath(cur.path, d); | |
tr("found!", opt); | |
lim = opt.length(); | |
// d+mdは減少することはないのでこれより短い解はキュー内には存在しない。 | |
break; | |
} | |
// 距離メモ大過去削除 | |
if(dm.size() > MEMOLIM){ | |
Iterator<Map.Entry<Long, Integer>> itr = dm.entrySet().iterator(); | |
int f = dm.size() - MEMOLIM; | |
while(itr.hasNext() && f-- >= 0){ | |
itr.next(); itr.remove(); | |
} | |
} | |
int ilind = d < 1 ? -1 : ((cur.path.get(2*d-2)?2:0)+(cur.path.get(2*d-1)?1:0))^1; | |
// 隣接移動 | |
for(int[] nei : NEIS[z]){ | |
if(nei[1] == ilind)continue; // 直前と逆の動きならスルー | |
int val = getl(v, nei[0]); | |
long[] nv = Arrays.copyOf(v, 4); | |
writel(nv, z, val); | |
writel(nv, nei[0], 62); | |
long enn = enc(nv); | |
Integer D = dm.get(enn); | |
if(D != null && D <= d+1)continue; | |
int mdd = dist(nv, h, w); | |
// d+mdは減少することはないのでlim以上は要らない | |
if(d + 1 + mdd < lim){ | |
dm.put(enn, d+1); | |
BitSet npath = new BitSet(); | |
npath.or(cur.path); | |
npath.set(2*(d+1)-2, (nei[1]&2)!=0); | |
npath.set(2*(d+1)-1, (nei[1]&1)!=0); | |
q.add(new Datum(nv, npath, nei[0], d+1, mdd)); | |
} | |
} | |
// 反復深化 | |
if(q.size() >= IDLIM){ | |
for(int f = q.size();f >= IDLIM;f--){ | |
q.pollLast(); | |
} | |
} | |
} | |
if(opt.length() > 0){ | |
// 解が存在する場合表示 | |
tr(opt.length(), opt, dm.size()); | |
out.println(opt); | |
out.flush(); | |
ct++; | |
}else{ | |
// 解が存在しない場合失敗 | |
tr("failed", dm.size()); | |
out.println(); | |
out.flush(); | |
} | |
long G = System.currentTimeMillis(); | |
tr(G-S+"ms"); | |
}else{ | |
out.println(); | |
} | |
} | |
tr(ct); | |
} | |
// 状態 | |
static class Datum | |
{ | |
public long[] state; // 盤面状態 | |
public BitSet path; // 状態に至るまでのパス。1手あたり2bitで格納する | |
public int d; // 状態に至るまでのパスの長さ | |
public int z; // 空白の位置 | |
public int md; // 評価関数 | |
public long hash; // ハッシュ値 | |
public Datum(long[] state, BitSet path, int z, int d, int h, int w) { | |
this.state = state; | |
hash = enc(state); | |
md = dist(state, h, w); | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
public Datum(long[] state, BitSet path, int z, int d, int md) { | |
this.state = state; | |
hash = enc(state); | |
this.md = md; | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
} | |
/** | |
* BitSetパスをStringパスに伸長 | |
* @param bs | |
* @param n | |
* @return | |
*/ | |
static String expandPath(BitSet bs, int n) | |
{ | |
char[] ret = new char[n]; | |
for(int i = 0;i < n;i++){ | |
ret[i] = udlr[(bs.get(2*i)?2:0)+(bs.get(2*i+1)?1:0)]; | |
} | |
return new String(ret); | |
} | |
// 状態から特定の座標のセルの値を取り出す | |
static int getl(long[] v, int u) | |
{ | |
return (int)(v[u/10]>>>(u%10*6))&63; | |
} | |
// 状態の特定の座標のセルの値を書き換える | |
static void writel(long[] v, int u, long z) | |
{ | |
v[u/10] &= ~(63L<<(u%10*6)); | |
v[u/10] |= z<<(u%10*6); | |
} | |
static int[] dr = {-1,1,0,0}; | |
static int[] dc = {0,0,-1,1}; | |
// 評価値計算用テーブル作成 | |
static boolean makeDistTable(int h, int w, long obs) | |
{ | |
tr("split begin"); | |
// (hw)^x<=LIM | |
// x<=logLIM/log hw | |
int x = 4; | |
int div = (h*w - Long.bitCount(obs) - 1 + x - 1) / x; | |
long[] sp = split(h, w, obs|1L<<h*w-1, div); | |
if(sp == null)return false; | |
tr("split end"); | |
tr("make begin"); | |
int hw = h*w; | |
SMAP = new int[hw]; | |
SP = 0; | |
for(int i = 0;i < h*w;i++){ | |
if(obs<<63-i>=0){ | |
SMAP[i] = SP++; | |
} | |
} | |
ST = new int[div][][][][][][]; | |
SETS = new int[div][]; | |
for(int i = 0;i < div;i++){ | |
int bc = Long.bitCount(sp[i]); | |
tr(i, bc); | |
if(bc == 3){ | |
ST[i] = new int[][][][][][]{{{simulate3(h, w, obs, sp[i])}}}; | |
}else if(bc == 4){ | |
ST[i] = new int[][][][][][]{{simulate4(h, w, obs, sp[i])}}; | |
}else if(bc == 5){ | |
ST[i] = new int[][][][][][]{simulate5(h, w, obs, sp[i])}; | |
} | |
int[] o = new int[bc]; | |
long t = sp[i]; | |
for(int j = 0;j < bc;j++,t&=t-1){ | |
o[j] = Long.numberOfTrailingZeros(t); | |
} | |
SETS[i] = o; | |
} | |
tr("make end"); | |
return true; | |
} | |
// 要素数3の集合についてテーブルを作成 | |
static int[][][] simulate3(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[3]; | |
for(int i = 0;i < 3;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][] d = new int[SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
Arrays.fill(d[i][j], 99999); | |
} | |
} | |
int[][] q = new int[SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 3;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 3;m++){ | |
if(nei[0] == cur[m])continue o1; | |
} | |
int[] no = Arrays.copyOf(cur, 3); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数4の集合についてテーブルを作成 | |
static int[][][][] simulate4(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[4]; | |
for(int i = 0;i < 4;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][][] d = new int[SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
Arrays.fill(d[i][j][k], 99999); | |
} | |
} | |
} | |
int[][] q = new int[SP*SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 4;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 4;m++){ | |
if(nei[0] == cur[m])continue o1; | |
} | |
int[] no = Arrays.copyOf(cur, 4); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]][SMAP[cur[3]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数5の集合についてテーブルを作成 | |
static int[][][][][] simulate5(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[5]; | |
int oc = 0; | |
for(int i = 0;i < 5;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
oc |= o[i]<<(6*i); | |
} | |
int[][][][][] d = new int[SP][SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
for(int l = 0;l < SP;l++){ | |
Arrays.fill(d[i][j][k][l], 99999); | |
} | |
} | |
} | |
} | |
Queue<Integer> q = new ArrayDeque<Integer>(); | |
// int[] q = new int[SP*SP*SP*SP*SP]; | |
q.add(oc); | |
// q[0] = oc; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]][SMAP[o[4]]] = 0; | |
// int r = 1; | |
// for(int p = 0;p < r;p++){ | |
int[] curo = new int[5]; | |
while(!q.isEmpty()){ | |
int cur = q.poll(); | |
for(int i = 0;i < 5;i++){ | |
curo[i] = cur>>6*i&63; | |
} | |
int curd = d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]]; | |
for(int l = 0;l < 5;l++){ | |
int nya = curo[l]; | |
o1: | |
for(int[] nei : NEIS[nya]){ | |
for(int m = 0;m < 5;m++){ | |
if(nei[0] == curo[m])continue o1; | |
} | |
curo[l] = nei[0]; | |
if(d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] == 99999){ | |
d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] = curd + 1; | |
int code = 0; | |
for(int i = 0;i < 5;i++){ | |
code |= curo[i]<<(6*i); | |
} | |
q.add(code); | |
// q[r++] = code; | |
} | |
} | |
curo[l] = nya; | |
} | |
} | |
return d; | |
} | |
// 盤面の最適分割を乱択で計算 | |
static long[] split(int N, int M, long obs, int D) | |
{ | |
long[] opt = null; | |
Random gen = new Random(); | |
int left = N*M-Long.bitCount(obs) - D; | |
long mask = (1L<<N*M)-1; | |
long lmask = 0; | |
long rmask = 0; | |
for(int i = 0;i < N;i++){ | |
lmask |= 1L<<i*M; | |
rmask |= 1L<<i*M+M-1; | |
} | |
lmask = ~lmask; | |
rmask = ~rmask; | |
long S = System.currentTimeMillis(); | |
int maxconn = 0; | |
outer: | |
for(int o = 0;o < 100000;o++){ | |
long[] b = new long[D]; | |
long all = obs; | |
for(int i = 0;i < D;i++){ | |
int pos = -1; | |
do{ | |
pos = gen.nextInt(N*M); | |
}while(all<<63-pos<0); | |
b[i] |= 1L<<pos; | |
all |= 1L<<pos; | |
} | |
for(int i = 0;i < left;i++){ | |
int c = i % D; | |
long nei = (b[c]<<M|b[c]>>M|(b[c]&lmask)>>1|(b[c]&rmask)<<1)&~all&mask; | |
if(nei == 0)continue outer; | |
int q = gen.nextInt(Long.bitCount(nei)); | |
for(int j = 1;j <= q;j++, nei&=nei-1); | |
long chosen = nei&-nei; | |
b[c] |= chosen; | |
all |= chosen; | |
} | |
int conn = 0; | |
for(int i = 0;i < D;i++){ | |
conn += Long.bitCount((b[i]<<M)&b[i]); | |
conn += Long.bitCount((b[i]>>M)&b[i]); | |
conn += Long.bitCount(((b[i]&lmask)>>1)&b[i]); | |
conn += Long.bitCount(((b[i]&rmask)<<1)&b[i]); | |
} | |
if(conn > maxconn){ | |
maxconn = conn; | |
opt = Arrays.copyOf(b, D); | |
} | |
} | |
long G = System.currentTimeMillis(); | |
if(opt != null){ | |
char[][] U = new char[N][M]; | |
for(int i = 0;i < N;i++){ | |
for(int j = 0;j < M;j++){ | |
int q = i*M+j; | |
if(obs<<63-q<0){ | |
U[i][j] = '#'; | |
continue; | |
} | |
for(int k = 0;k < D;k++){ | |
if(opt[k]<<63-q<0){ | |
U[i][j] = (char)('A'+k); | |
break; | |
} | |
} | |
} | |
} | |
for(char[] row : U){ | |
tr(row); | |
} | |
} | |
tr(G-S+"ms"); | |
return opt; | |
} | |
// 評価値計算 | |
static int dist(long[] v, int h, int w) | |
{ | |
int ret = 0; | |
int[] ipos = new int[h*w]; | |
int hw = h*w; | |
int p = 0; | |
for(int i = 0;i < 4;i++){ | |
for(int j = 0;j < 60;j += 6, p++){ | |
if(p >= hw)break; | |
int e = (int)(v[i]>>>j)&63; | |
if(e < 62)ipos[e-1] = p; | |
} | |
} | |
for(int i = 0;i < SETS.length;i++){ | |
int l = SETS[i].length; | |
int[] x = new int[6]; | |
for(int j = 0;j < l;j++){ | |
x[6-l+j] = ipos[SETS[i][j]]; | |
} | |
ret += ST[i][SMAP[x[0]]][SMAP[x[1]]][SMAP[x[2]]][SMAP[x[3]]][SMAP[x[4]]][SMAP[x[5]]]; | |
} | |
return ret; | |
} | |
// 盤面情報の圧縮 | |
static long[] shrink(int[][] b) | |
{ | |
long[] ret = new long[4]; | |
int h = b.length; | |
int w = b[0].length; | |
int p = 0; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int v = b[i][j]; | |
if(v == 0)v = 62; | |
if(v == -1)v = 63; | |
ret[p/10] |= ((long)v) << (p%10*6); | |
p++; | |
} | |
} | |
return ret; | |
} | |
// 展開 | |
// static int[][] expand(long[] v, int h, int w) | |
// { | |
// int[][] ret = new int[h][w]; | |
// int p = 0; | |
// for(int i = 0;i < 4;i++){ | |
// for(int j = 0;j < 60;j += 6){ | |
// if(p >= h*w)break; | |
// int e = (int)(v[i]>>>j)&63; | |
// if(e == 63)e = -1; | |
// if(e == 62)e = 0; | |
// ret[p/w][p%w] = e; | |
// p++; | |
// } | |
// } | |
// return ret; | |
// } | |
// ハッシュ値計算 | |
static long enc(long[] u) | |
{ | |
return (((u[3]+(u[3]>>>32))*37+(u[2]+(u[2]>>>32)))*37+(u[1]+(u[1]>>>32)))*37+(u[0]+(u[0]>>>32)); | |
} | |
// 入力文字を数値に変換 | |
static int dec(char x) | |
{ | |
if(x == '=')return -1; | |
if(x >= '0' && x <= '9')return x - '0'; | |
return x - 'A' + 10; | |
} | |
public static void main(String[] args) throws Exception | |
{ | |
long s = System.currentTimeMillis(); | |
in = INPUT.isEmpty() ? new Scanner(new File("x:\\input.txt")) : new Scanner(INPUT); | |
in2 = new Scanner(new File("x:\\output.txt")); | |
out = new PrintWriter("x:\\output" + (new SimpleDateFormat("MMddHHmm")).format(new Date()) + ".txt"); | |
// out = new PrintWriter(System.out); | |
solve(); | |
out.flush(); | |
tr(System.currentTimeMillis() - s+"ms"); | |
} | |
static int ni() { return Integer.parseInt(in.next()); } | |
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.PrintWriter; | |
import java.text.SimpleDateFormat; | |
import java.util.ArrayDeque; | |
import java.util.Arrays; | |
import java.util.BitSet; | |
import java.util.Comparator; | |
import java.util.Date; | |
import java.util.Iterator; | |
import java.util.LinkedHashMap; | |
import java.util.Map; | |
import java.util.Queue; | |
import java.util.Random; | |
import java.util.Scanner; | |
import java.util.TreeSet; | |
/** | |
* IDA*特化型 | |
* 20110911 | |
* @author uwi | |
* | |
*/ | |
public class FIDA2 { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static char[] udlr = "UDLR".toCharArray(); | |
static int[][][][][][][] ST; // 評価値計算用テーブル | |
static int[][] SETS; // 分割済集合の構成要素 | |
static int[] SMAP; // シェイクシェイクブギーな胸騒ぎ | |
static int SP; // STの単位=壁以外のセルの個数 | |
static int IDLIM = 600000; // キューの最大要素数 | |
static int MEMOLIM = 4000000; // メモの最大状態数 | |
static Random gen = new Random(2011); | |
static int[][][] NEIS; // 隣接移動情報格納用 | |
// 状態比較関数 | |
// 距離+評価関数昇順, 評価関数昇順, ハッシュ値昇順 | |
static Comparator<Datum> comp = new Comparator<Datum>(){ | |
public int compare(Datum a, Datum b){ | |
// if((a.d + a.md) - (b.d + b.md) != 0)return (a.d + a.md) - (b.d + b.md); | |
if(a.md - b.md != 0)return a.md - b.md; | |
return Long.signum(a.hash - b.hash); | |
}; | |
}; | |
static void solve() | |
{ | |
ni(); ni(); ni(); ni(); | |
int n = ni(); | |
int ct = 0; | |
in.nextLine(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String[] sp = line.split(","); | |
int w = Integer.parseInt(sp[0]); | |
int h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
// 数値盤面作成 | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
int ozr = 0, ozc = 0; | |
long obs = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
if(b[j][k] == 0){ | |
ozr = j; ozc = k; | |
} | |
if(b[j][k] == -1){ | |
obs |= 1L<<j*w+k; | |
} | |
} | |
} | |
// 探索手数上限を設定 | |
String line2; | |
int len; | |
if(in2 != null){ | |
line2 = in2.nextLine(); | |
len = line2.length(); | |
}else{ | |
line2 = ""; | |
len = 0; | |
} | |
int lim = len == 0 ? 150 : len; | |
if(o>=0){ // 絞り込み条件 | |
long S = System.currentTimeMillis(); | |
tr(o, h, w, sp[2], alive, lim); | |
// 隣接移動キャッシュ作成 | |
NEIS = new int[h*w][][]; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int B = 0; | |
for(int k = 0;k < 4;k++){ | |
int nr = i + dr[k]; | |
int nc = j + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
B |= 1<<k; | |
} | |
} | |
NEIS[i*w+j] = new int[Integer.bitCount(B)][2]; | |
int c = 0; | |
for(int k = 0;k <= 3;k++){ | |
if(B<<31-k<0){ | |
NEIS[i*w+j][c][0] = (i+dr[k])*w + (j+dc[k]); | |
NEIS[i*w+j][c][1] = k; | |
c++; | |
} | |
} | |
} | |
} | |
// 評価値テーブル作成 | |
if(!makeDistTable(h, w, obs)){ | |
tr("failed to make distTable!"); | |
out.println(); | |
out.flush(); | |
continue; | |
} | |
// 理想状態のハッシュ値を計算しておく | |
int[][] ideal = new int[h][w]; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
ideal[j][k] = b[j][k] == -1 ? -1 : j*w+k+1; | |
} | |
} | |
ideal[h-1][w-1] = 0; | |
long ei = enc(shrink(ideal)); | |
// 初期状態の作成 | |
Map<Long, Integer> dm = new LinkedHashMap<Long, Integer>(); | |
String opt = ""; | |
Queue<Datum> q = new ArrayDeque<Datum>(); | |
TreeSet<Datum> nq = new TreeSet<Datum>(comp); | |
nq.add(new Datum(shrink(b), new BitSet(), ozr*w+ozc, 0, h, w)); | |
Runtime rt = Runtime.getRuntime(); | |
int step = 0; | |
out: | |
while(!nq.isEmpty()){ | |
for(Datum tum : nq)q.add(tum); | |
nq.clear(); | |
while(!q.isEmpty()){ | |
Datum cur = q.poll(); | |
if(++step % 20000 == 0){ | |
// ステップ数, キューのサイズ, 現在探索中のパスの長さ, 現在探索中のノードの評価値, 距離キャッシュのサイズ, 使用中のメモリ, 探索上限 | |
tr(step, q.size(), nq.size(), cur.d, cur.md, dm.size(), rt.totalMemory() - rt.freeMemory(), lim); | |
} | |
long[] v = cur.state; | |
int z = cur.z; | |
// cache check | |
int d = cur.d; | |
if(d >= lim)continue; | |
// 終了状態なら最適手順に登録 | |
if(cur.hash == ei && (opt.length() == 0 || d < opt.length())){ | |
opt = expandPath(cur.path, d); | |
tr("found!", opt); | |
lim = opt.length(); | |
// d+mdは減少することはないのでこれより短い解はキュー内には存在しない。 | |
break out; | |
} | |
// 距離メモ大過去削除 | |
if(dm.size() > MEMOLIM){ | |
Iterator<Map.Entry<Long, Integer>> itr = dm.entrySet().iterator(); | |
int f = dm.size() - MEMOLIM; | |
while(itr.hasNext() && f-- >= 0){ | |
itr.next(); itr.remove(); | |
} | |
} | |
int ilind = d < 1 ? -1 : ((cur.path.get(2*d-2)?2:0)+(cur.path.get(2*d-1)?1:0))^1; | |
// 隣接移動 | |
for(int[] nei : NEIS[z]){ | |
if(nei[1] == ilind)continue; // 直前と逆の動きならスルー | |
int np = nei[0]; | |
int nz = getl(v, np); | |
long[] nv = Arrays.copyOf(v, 4); | |
writel(nv, z, nz); | |
writel(nv, np, 62); | |
long enn = enc(nv); | |
Integer D = dm.get(enn); | |
if(D != null && D <= d+1)continue; | |
int mdd = dist(nv, h, w); | |
// d+mdは減少することはないのでlim以上は要らない | |
if(d + 1 + mdd < lim){ | |
// nqに追加するとき、すでにnqがいっぱいであれば、最終要素と比較しておく | |
if(d+1+mdd > d+cur.md && nq.size() >= IDLIM && mdd > nq.last().md){ | |
continue; | |
} | |
dm.put(enn, d+1); | |
BitSet npath = new BitSet(); | |
npath.or(cur.path); | |
npath.set(2*(d+1)-2, (nei[1]&2)!=0); | |
npath.set(2*(d+1)-1, (nei[1]&1)!=0); | |
Datum next = new Datum(nv, npath, np, d+1, mdd); | |
if(d+1+mdd == d+cur.md){ | |
q.add(next); | |
}else{ | |
nq.add(next); | |
} | |
} | |
} | |
// 反復深化 | |
if(nq.size() >= IDLIM){ | |
for(int f = nq.size();f >= IDLIM;f--){ | |
nq.pollLast(); | |
} | |
} | |
} | |
} | |
if(opt.length() > 0){ | |
// 解が存在する場合表示 | |
tr(opt.length(), opt, dm.size()); | |
out.println(opt); | |
out.flush(); | |
ct++; | |
}else{ | |
// 解が存在しない場合失敗 | |
tr("failed", dm.size()); | |
out.println(); | |
out.flush(); | |
} | |
long G = System.currentTimeMillis(); | |
tr(G-S+"ms"); | |
}else{ | |
out.println(); | |
out.flush(); | |
} | |
} | |
tr(ct); | |
} | |
// 状態 | |
static class Datum | |
{ | |
public long[] state; // 盤面状態 | |
public BitSet path; // 状態に至るまでのパス。1手あたり2bitで格納する | |
public int d; // 状態に至るまでのパスの長さ | |
public int z; // 空白の位置 | |
public int md; // 評価関数 | |
public long hash; // ハッシュ値 | |
public Datum(long[] state, BitSet path, int z, int d, int h, int w) { | |
this.state = state; | |
hash = enc(state); | |
md = dist(state, h, w); | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
public Datum(long[] state, BitSet path, int z, int d, int md) { | |
this.state = state; | |
hash = enc(state); | |
this.md = md; | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
} | |
/** | |
* BitSetパスをStringパスに伸長 | |
* @param bs | |
* @param n | |
* @return | |
*/ | |
static String expandPath(BitSet bs, int n) | |
{ | |
char[] ret = new char[n]; | |
for(int i = 0;i < n;i++){ | |
ret[i] = udlr[(bs.get(2*i)?2:0)+(bs.get(2*i+1)?1:0)]; | |
} | |
return new String(ret); | |
} | |
// 状態から特定の座標のセルの値を取り出す | |
static int getl(long[] v, int u) | |
{ | |
return (int)(v[u/10]>>>(u%10*6))&63; | |
} | |
// 状態の特定の座標のセルの値を書き換える | |
static void writel(long[] v, int u, long z) | |
{ | |
v[u/10] &= ~(63L<<(u%10*6)); | |
v[u/10] |= z<<(u%10*6); | |
} | |
static int[] dr = {-1,1,0,0}; | |
static int[] dc = {0,0,-1,1}; | |
// 評価値計算用テーブル作成 | |
static boolean makeDistTable(int h, int w, long obs) | |
{ | |
tr("split begin"); | |
// (hw)^x<=LIM | |
// x<=logLIM/log hw | |
int x = (int)(Math.log(20000000)/Math.log(h*w)); | |
x = h*w - Long.bitCount(obs) >= 31 ? 4 : 5; | |
int div = (h*w - Long.bitCount(obs) - 1 + x - 1) / x; | |
long[] sp = split(h, w, obs|1L<<h*w-1, div); | |
tr("split end"); | |
if(sp == null)return false; | |
tr("make begin"); | |
int hw = h*w; | |
SMAP = new int[hw]; | |
SP = 0; | |
for(int i = 0;i < h*w;i++){ | |
if(obs<<63-i>=0){ | |
SMAP[i] = SP++; | |
} | |
} | |
ST = new int[div][][][][][][]; | |
SETS = new int[div][]; | |
for(int i = 0;i < div;i++){ | |
int bc = Long.bitCount(sp[i]); | |
tr(i, bc); | |
if(bc == 3){ | |
ST[i] = new int[][][][][][]{{{simulate3(h, w, obs, sp[i])}}}; | |
}else if(bc == 4){ | |
ST[i] = new int[][][][][][]{{simulate4(h, w, obs, sp[i])}}; | |
}else if(bc == 5){ | |
ST[i] = new int[][][][][][]{simulate5(h, w, obs, sp[i])}; | |
} | |
int[] o = new int[bc]; | |
long t = sp[i]; | |
for(int j = 0;j < bc;j++,t&=t-1){ | |
o[j] = Long.numberOfTrailingZeros(t); | |
} | |
SETS[i] = o; | |
} | |
tr("make end"); | |
return true; | |
} | |
// 要素数3の集合についてテーブルを作成 | |
static int[][][] simulate3(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[3]; | |
for(int i = 0;i < 3;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][] d = new int[SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
Arrays.fill(d[i][j], 99999); | |
} | |
} | |
int[][] q = new int[SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 3;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 3;m++){ | |
if(nei[0] == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 3); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数4の集合についてテーブルを作成 | |
static int[][][][] simulate4(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[4]; | |
for(int i = 0;i < 4;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][][] d = new int[SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
Arrays.fill(d[i][j][k], 99999); | |
} | |
} | |
} | |
int[][] q = new int[SP*SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 4;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 4;m++){ | |
if(nei[0] == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 4); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]][SMAP[cur[3]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数5の集合についてテーブルを作成 | |
static int[][][][][] simulate5(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[5]; | |
int oc = 0; | |
for(int i = 0;i < 5;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
oc |= o[i]<<(6*i); | |
} | |
int[][][][][] d = new int[SP][SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
for(int l = 0;l < SP;l++){ | |
Arrays.fill(d[i][j][k][l], 99999); | |
} | |
} | |
} | |
} | |
Queue<Integer> q = new ArrayDeque<Integer>(); | |
q.add(oc); | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]][SMAP[o[4]]] = 0; | |
int[] curo = new int[5]; | |
while(!q.isEmpty()){ | |
int cur = q.poll(); | |
long hit = 0; | |
for(int i = 0;i < 5;i++){ | |
curo[i] = cur>>6*i&63; | |
hit |= 1L<<curo[i]; | |
} | |
int curd = d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]]; | |
for(int l = 0;l < 5;l++){ | |
int nya = curo[l]; | |
cur ^= curo[l]<<6*l; | |
for(int[] nei : NEIS[nya]){ | |
if(hit<<63-nei[0]<0)continue; | |
curo[l] = nei[0]; | |
if(d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] == 99999){ | |
d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] = curd + 1; | |
q.add(cur^curo[l]<<6*l); | |
} | |
} | |
curo[l] = nya; | |
cur ^= curo[l]<<6*l; | |
} | |
} | |
return d; | |
} | |
// 盤面の最適分割を乱択で計算 | |
static long[] split(int N, int M, long obs, int D) | |
{ | |
long[] opt = null; | |
Random gen = new Random(); | |
int left = N*M-Long.bitCount(obs) - D; | |
long mask = (1L<<N*M)-1; | |
long lmask = 0; | |
long rmask = 0; | |
for(int i = 0;i < N;i++){ | |
lmask |= 1L<<i*M; | |
rmask |= 1L<<i*M+M-1; | |
} | |
lmask = ~lmask; | |
rmask = ~rmask; | |
long S = System.currentTimeMillis(); | |
int maxconn = 0; | |
outer: | |
for(int o = 0;o < 100000;o++){ | |
long[] b = new long[D]; | |
long all = obs; | |
for(int i = 0;i < D;i++){ | |
int pos = -1; | |
do{ | |
pos = gen.nextInt(N*M); | |
}while(all<<63-pos<0); | |
b[i] |= 1L<<pos; | |
all |= 1L<<pos; | |
} | |
for(int i = 0;i < left;i++){ | |
int c = i % D; | |
long nei = (b[c]<<M|b[c]>>M|(b[c]&lmask)>>1|(b[c]&rmask)<<1)&~all&mask; | |
if(nei == 0)continue outer; | |
int q = gen.nextInt(Long.bitCount(nei)); | |
for(int j = 1;j <= q;j++, nei&=nei-1); | |
long chosen = nei&-nei; | |
b[c] |= chosen; | |
all |= chosen; | |
} | |
int conn = 0; | |
for(int i = 0;i < D;i++){ | |
conn += Long.bitCount((b[i]<<M)&b[i]); | |
conn += Long.bitCount((b[i]>>M)&b[i]); | |
conn += Long.bitCount(((b[i]&lmask)>>1)&b[i]); | |
conn += Long.bitCount(((b[i]&rmask)<<1)&b[i]); | |
} | |
if(conn > maxconn){ | |
maxconn = conn; | |
opt = Arrays.copyOf(b, D); | |
} | |
} | |
long G = System.currentTimeMillis(); | |
if(opt != null){ | |
char[][] U = new char[N][M]; | |
for(int i = 0;i < N;i++){ | |
for(int j = 0;j < M;j++){ | |
int q = i*M+j; | |
if(obs<<63-q<0){ | |
U[i][j] = '#'; | |
continue; | |
} | |
for(int k = 0;k < D;k++){ | |
if(opt[k]<<63-q<0){ | |
U[i][j] = (char)('A'+k); | |
break; | |
} | |
} | |
} | |
} | |
for(char[] row : U){ | |
tr(row); | |
} | |
} | |
tr(G-S+"ms"); | |
return opt; | |
} | |
// 評価値計算 | |
static int dist(long[] v, int h, int w) | |
{ | |
int ret = 0; | |
int[] ipos = new int[h*w]; | |
int hw = h*w; | |
int p = 0; | |
for(int i = 0;i < 4;i++){ | |
for(int j = 0;j < 60;j += 6, p++){ | |
if(p >= hw)break; | |
int e = (int)(v[i]>>>j)&63; | |
if(e < 62)ipos[e-1] = p; | |
} | |
} | |
for(int i = 0;i < SETS.length;i++){ | |
int l = SETS[i].length; | |
int[] x = new int[6]; | |
for(int j = 0;j < l;j++){ | |
x[6-l+j] = ipos[SETS[i][j]]; | |
} | |
ret += ST[i][SMAP[x[0]]][SMAP[x[1]]][SMAP[x[2]]][SMAP[x[3]]][SMAP[x[4]]][SMAP[x[5]]]; | |
} | |
return ret; | |
} | |
// 盤面情報の圧縮 | |
static long[] shrink(int[][] b) | |
{ | |
long[] ret = new long[4]; | |
int h = b.length; | |
int w = b[0].length; | |
int p = 0; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int v = b[i][j]; | |
if(v == 0)v = 62; | |
if(v == -1)v = 63; | |
ret[p/10] |= ((long)v) << (p%10*6); | |
p++; | |
} | |
} | |
return ret; | |
} | |
// 展開 | |
// static int[][] expand(long[] v, int h, int w) | |
// { | |
// int[][] ret = new int[h][w]; | |
// int p = 0; | |
// for(int i = 0;i < 4;i++){ | |
// for(int j = 0;j < 60;j += 6){ | |
// if(p >= h*w)break; | |
// int e = (int)(v[i]>>>j)&63; | |
// if(e == 63)e = -1; | |
// if(e == 62)e = 0; | |
// ret[p/w][p%w] = e; | |
// p++; | |
// } | |
// } | |
// return ret; | |
// } | |
// ハッシュ値計算 | |
static long enc(long[] u) | |
{ | |
return (((u[3]+(u[3]>>>32))*37+(u[2]+(u[2]>>>32)))*37+(u[1]+(u[1]>>>32)))*37+(u[0]+(u[0]>>>32)); | |
} | |
// 入力文字を数値に変換 | |
static int dec(char x) | |
{ | |
if(x == '=')return -1; | |
if(x >= '0' && x <= '9')return x - '0'; | |
return x - 'A' + 10; | |
} | |
public static void main(String[] args) throws Exception | |
{ | |
long s = System.currentTimeMillis(); | |
in = INPUT.isEmpty() ? new Scanner(new File("x:\\input.txt")) : new Scanner(INPUT); | |
in2 = new Scanner(new File("x:\\output.txt")); | |
out = new PrintWriter("x:\\output" + (new SimpleDateFormat("MMddHHmm")).format(new Date()) + ".txt"); | |
// out = new PrintWriter(System.out); | |
solve(); | |
out.flush(); | |
tr(System.currentTimeMillis() - s+"ms"); | |
} | |
static int ni() { return Integer.parseInt(in.next()); } | |
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package gdd2011; | |
import java.io.File; | |
import java.io.FileNotFoundException; | |
import java.io.FileOutputStream; | |
import java.io.IOException; | |
import java.io.OutputStream; | |
import java.io.PrintWriter; | |
import java.io.RandomAccessFile; | |
import java.text.SimpleDateFormat; | |
import java.util.ArrayDeque; | |
import java.util.Arrays; | |
import java.util.BitSet; | |
import java.util.Comparator; | |
import java.util.Date; | |
import java.util.Iterator; | |
import java.util.LinkedHashMap; | |
import java.util.Map; | |
import java.util.Queue; | |
import java.util.Random; | |
import java.util.Scanner; | |
import java.util.TreeSet; | |
/** | |
* 評価関数テーブルをファイルに退避するIDA* | |
* 20110912 | |
* @author uwi | |
* | |
*/ | |
public class FIDAM2 { | |
static Scanner in, in2; | |
static PrintWriter out; | |
static String INPUT = ""; | |
static char[] udlr = "UDLR".toCharArray(); | |
static RandomAccessFile[] RAFS; | |
static String RAFPATH = "x:\\dist"; | |
static int[][][][][] ST; // 評価値計算用テーブル | |
static int[][] SETS; // 分割済集合の構成要素 | |
static int[] SMAP; // シェイクシェイクブギーな胸騒ぎ | |
static int SP; // STの単位=壁以外のセルの個数 | |
static int IDLIM = 1000000; // キューの最大要素数 | |
static int MEMOLIM = 1000000; // メモの最大状態数 | |
static Random gen = new Random(20110); | |
static int[][][] NEIS; // 隣接移動情報格納用 | |
// 状態比較関数 | |
// 距離+評価関数昇順, 評価関数昇順, ハッシュ値昇順 | |
static Comparator<Datum> comp = new Comparator<Datum>(){ | |
public int compare(Datum a, Datum b){ | |
if(a.md - b.md != 0)return a.md - b.md; | |
return Long.signum(a.hash - b.hash); | |
}; | |
}; | |
static void solve() | |
{ | |
Runtime rt = Runtime.getRuntime(); | |
ni(); ni(); ni(); ni(); | |
int n = ni(); | |
int ct = 0; | |
in.nextLine(); | |
for(int o = 0;o < n;o++){ | |
String line = in.nextLine(); | |
String[] sp = line.split(","); | |
int w = Integer.parseInt(sp[0]); | |
int h = Integer.parseInt(sp[1]); | |
char[] u = sp[2].toCharArray(); | |
// 数値盤面作成 | |
int[][] b = new int[h][w]; | |
int alive = 0; | |
int ozr = 0, ozc = 0; | |
long obs = 0; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
b[j][k] = dec(u[j*w+k]); | |
if(b[j][k] != -1)alive++; | |
if(b[j][k] == 0){ | |
ozr = j; ozc = k; | |
} | |
if(b[j][k] == -1){ | |
obs |= 1L<<j*w+k; | |
} | |
} | |
} | |
// 探索手数上限を設定 | |
String line2; | |
int len; | |
if(in2 != null){ | |
line2 = in2.nextLine(); | |
len = line2.length(); | |
}else{ | |
line2 = ""; | |
len = 0; | |
} | |
int lim = len == 0 ? 190 : len; | |
if(o >= 0){ // 絞り込み条件 | |
long S = System.currentTimeMillis(); | |
tr(o, h, w, sp[2], alive, lim); | |
// 隣接移動キャッシュ作成 | |
NEIS = new int[h*w][][]; | |
for(int i = 0;i < h;i++){ | |
for(int j = 0;j < w;j++){ | |
int B = 0; | |
for(int k = 0;k < 4;k++){ | |
int nr = i + dr[k]; | |
int nc = j + dc[k]; | |
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){ | |
B |= 1<<k; | |
} | |
} | |
NEIS[i*w+j] = new int[Integer.bitCount(B)][2]; | |
int c = 0; | |
for(int k = 0;k <= 3;k++){ | |
if(B<<31-k<0){ | |
NEIS[i*w+j][c][0] = (i+dr[k])*w + (j+dc[k]); | |
NEIS[i*w+j][c][1] = k; | |
c++; | |
} | |
} | |
} | |
} | |
// 評価値テーブル作成 | |
if(!makeDistTable(h, w, obs)){ | |
tr("failed to make distTable!"); | |
out.println(); | |
out.flush(); | |
continue; | |
} | |
// 理想状態のハッシュ値を計算しておく | |
int[][] ideal = new int[h][w]; | |
for(int j = 0;j < h;j++){ | |
for(int k = 0;k < w;k++){ | |
ideal[j][k] = b[j][k] == -1 ? -1 : j*w+k+1; | |
} | |
} | |
ideal[h-1][w-1] = 0; | |
long ei = enc(shrink(ideal)); | |
// 初期状態の作成 | |
Map<Long, Integer> dm = new LinkedHashMap<Long, Integer>(); | |
String opt = ""; | |
Queue<Datum> q = new ArrayDeque<Datum>(); | |
TreeSet<Datum> nq = new TreeSet<Datum>(comp); | |
nq.add(new Datum(shrink(b), new BitSet(), ozr*w+ozc, 0, h, w)); | |
int step = 0; | |
out: | |
while(!nq.isEmpty()){ | |
for(Datum tum : nq)q.add(tum); | |
nq.clear(); | |
while(!q.isEmpty()){ | |
Datum cur = q.poll(); | |
if(++step % 20000 == 0){ | |
// ステップ数, キューのサイズ, 現在探索中のパスの長さ, 現在探索中のノードの評価値, 距離キャッシュのサイズ, 使用中のメモリ, 探索上限 | |
tr(step, q.size(), nq.size(), cur.d, cur.md, dm.size(), rt.totalMemory() - rt.freeMemory(), lim); | |
} | |
long[] v = cur.state; | |
int z = cur.z; | |
// cache check | |
int d = cur.d; | |
if(d >= lim)continue; | |
// 終了状態なら最適手順に登録 | |
if(cur.hash == ei && (opt.length() == 0 || d < opt.length())){ | |
opt = expandPath(cur.path, d); | |
tr("found!", opt); | |
lim = opt.length(); | |
// d+mdは減少することはないのでこれより短い解はキュー内には存在しない。 | |
break out; | |
} | |
// 距離メモ大過去削除 | |
if(dm.size() > MEMOLIM){ | |
Iterator<Map.Entry<Long, Integer>> itr = dm.entrySet().iterator(); | |
int f = dm.size() - MEMOLIM; | |
while(itr.hasNext() && f-- >= 0){ | |
itr.next(); itr.remove(); | |
} | |
} | |
int ilind = d < 1 ? -1 : ((cur.path.get(2*d-2)?2:0)+(cur.path.get(2*d-1)?1:0))^1; | |
// 隣接移動 | |
for(int[] nei : NEIS[z]){ | |
if(nei[1] == ilind)continue; // 直前と逆の動きならスルー | |
int np = nei[0]; | |
int nz = getl(v, np); | |
long[] nv = Arrays.copyOf(v, 4); | |
writel(nv, z, nz); | |
writel(nv, np, 62); | |
long enn = enc(nv); | |
Integer D = dm.get(enn); | |
if(D != null && D <= d+1)continue; | |
int mdd = dist(nv, h, w); | |
// d+mdは減少することはないのでlim以上は要らない | |
if(d + 1 + mdd < lim){ | |
// nqに追加するとき、すでにnqがいっぱいであれば、最終要素と比較しておく | |
if(d+1+mdd > d+cur.md && nq.size() >= IDLIM && mdd > nq.last().md){ | |
continue; | |
} | |
dm.put(enn, d+1); | |
BitSet npath = new BitSet(); | |
npath.or(cur.path); | |
npath.set(2*(d+1)-2, (nei[1]&2)!=0); | |
npath.set(2*(d+1)-1, (nei[1]&1)!=0); | |
Datum next = new Datum(nv, npath, np, d+1, mdd); | |
if(d+1+mdd == d+cur.md){ | |
q.add(next); | |
}else{ | |
nq.add(next); | |
} | |
} | |
} | |
// 反復深化 | |
if(nq.size() >= IDLIM){ | |
for(int f = nq.size();f >= IDLIM;f--){ | |
nq.pollLast(); | |
} | |
} | |
} | |
} | |
if(opt.length() > 0){ | |
// 解が存在する場合表示 | |
tr(opt.length(), opt, dm.size()); | |
out.println(opt); | |
out.flush(); | |
ct++; | |
}else{ | |
// 解が存在しない場合失敗 | |
tr("failed", dm.size()); | |
out.println(); | |
out.flush(); | |
} | |
long G = System.currentTimeMillis(); | |
tr(G-S+"ms"); | |
}else{ | |
out.println(); | |
} | |
} | |
tr(ct); | |
} | |
// 状態 | |
static class Datum | |
{ | |
public long[] state; // 盤面状態 | |
public BitSet path; // 状態に至るまでのパス。1手あたり2bitで格納する | |
public int d; // 状態に至るまでのパスの長さ | |
public int z; // 空白の位置 | |
public int md; // 評価関数 | |
public long hash; // ハッシュ値 | |
public Datum(long[] state, BitSet path, int z, int d, int h, int w) { | |
this.state = state; | |
hash = enc(state); | |
md = dist(state, h, w); | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
public Datum(long[] state, BitSet path, int z, int d, int md) { | |
this.state = state; | |
hash = enc(state); | |
this.md = md; | |
this.path = path; | |
this.d = d; | |
this.z = z; | |
} | |
} | |
/** | |
* BitSetパスをStringパスに伸長 | |
* @param bs | |
* @param n | |
* @return | |
*/ | |
static String expandPath(BitSet bs, int n) | |
{ | |
char[] ret = new char[n]; | |
for(int i = 0;i < n;i++){ | |
ret[i] = udlr[(bs.get(2*i)?2:0)+(bs.get(2*i+1)?1:0)]; | |
} | |
return new String(ret); | |
} | |
// 状態から特定の座標のセルの値を取り出す | |
static int getl(long[] v, int u) | |
{ | |
return (int)(v[u/10]>>>(u%10*6))&63; | |
} | |
// 状態の特定の座標のセルの値を書き換える | |
static void writel(long[] v, int u, long z) | |
{ | |
v[u/10] &= ~(63L<<(u%10*6)); | |
v[u/10] |= z<<(u%10*6); | |
} | |
static int[] dr = {-1,1,0,0}; | |
static int[] dc = {0,0,-1,1}; | |
// 評価値計算用テーブル作成 | |
static boolean makeDistTable(int h, int w, long obs) | |
{ | |
tr("split begin"); | |
int x = 5; | |
// x = h*w - Long.bitCount(obs) >= 31 ? 4 : 5; | |
int div = (h*w - Long.bitCount(obs) - 1 + x - 1) / x; | |
long[] sp = split(h, w, obs|1L<<h*w-1, div); | |
tr("split end"); | |
if(sp == null)return false; | |
tr("make begin"); | |
int hw = h*w; | |
SMAP = new int[hw]; | |
SP = 0; | |
for(int i = 0;i < h*w;i++){ | |
if(obs<<63-i>=0){ | |
SMAP[i] = SP++; | |
} | |
} | |
RAFS = new RandomAccessFile[div]; | |
ST = new int[div][][][][]; | |
SETS = new int[div][]; | |
try { | |
for(int i = 0;i < div;i++){ | |
int bc = Long.bitCount(sp[i]); | |
tr(i, bc); | |
if(RAFS[i] != null){ | |
RAFS[i].close(); | |
RAFS[i] = null; | |
} | |
if(bc == 3){ | |
ST[i] = new int[][][][]{simulate3(h, w, obs, sp[i])}; | |
}else if(bc == 4){ | |
ST[i] = simulate4(h, w, obs, sp[i]); | |
}else if(bc == 5){ | |
ST[i] = null; | |
byte[][][][][] table = simulate5(h, w, obs, sp[i]); | |
tr(i, bc, "write"); | |
OutputStream os = new FileOutputStream(RAFPATH + i, false); | |
for(int a = 0;a < SP;a++){ | |
for(int b = 0;b < SP;b++){ | |
for(int c = 0;c < SP;c++){ | |
for(int d = 0;d < SP;d++){ | |
os.write(table[a][b][c][d]); | |
} | |
} | |
} | |
} | |
os.close(); | |
RAFS[i] = new RandomAccessFile(RAFPATH + i, "r"); | |
// ST[i] = new int[][][][][][]{simulate5(h, w, obs, sp[i])}; | |
}else if(bc == 6){ | |
ST[i] = null; | |
byte[][][][][][] table = simulate6(h, w, obs, sp[i]); | |
tr(i, bc, "write"); | |
OutputStream os = new FileOutputStream(RAFPATH + i, false); | |
for(int a = 0;a < SP;a++){ | |
for(int b = 0;b < SP;b++){ | |
for(int c = 0;c < SP;c++){ | |
for(int d = 0;d < SP;d++){ | |
for(int e = 0;e < SP;e++){ | |
os.write(table[a][b][c][d][e]); | |
} | |
} | |
} | |
} | |
} | |
os.close(); | |
RAFS[i] = new RandomAccessFile(RAFPATH + i, "r"); | |
} | |
int[] o = new int[bc]; | |
long t = sp[i]; | |
for(int j = 0;j < bc;j++,t&=t-1){ | |
o[j] = Long.numberOfTrailingZeros(t); | |
} | |
SETS[i] = o; | |
} | |
} catch (FileNotFoundException e) { | |
} catch (IOException e) { | |
} | |
tr("make end"); | |
return true; | |
} | |
// 要素数3の集合についてテーブルを作成 | |
static int[][][] simulate3(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[3]; | |
for(int i = 0;i < 3;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][] d = new int[SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
Arrays.fill(d[i][j], 99999); | |
} | |
} | |
int[][] q = new int[SP*SP*SP][]; | |
q[0] = o; | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]] = 0; | |
int r = 1; | |
for(int p = 0;p < r;p++){ | |
int[] cur = q[p]; | |
for(int l = 0;l < 3;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 3;m++){ | |
if(nei[0] == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 3); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]] + 1; | |
q[r++] = no; | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数4の集合についてテーブルを作成 | |
static int[][][][] simulate4(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[4]; | |
for(int i = 0;i < 4;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
} | |
int[][][][] d = new int[SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
Arrays.fill(d[i][j][k], 99999); | |
} | |
} | |
} | |
Queue<int[]> q = new ArrayDeque<int[]>(); | |
q.add(o); | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]] = 0; | |
while(!q.isEmpty()){ | |
int[] cur = q.poll(); | |
for(int l = 0;l < 4;l++){ | |
o1: | |
for(int[] nei : NEIS[cur[l]]){ | |
for(int m = 0;m < 4;m++){ | |
if(nei[0] == cur[m]){ | |
continue o1; | |
} | |
} | |
int[] no = Arrays.copyOf(cur, 4); | |
no[l] = nei[0]; | |
if(d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] == 99999){ | |
d[SMAP[no[0]]][SMAP[no[1]]][SMAP[no[2]]][SMAP[no[3]]] = | |
d[SMAP[cur[0]]][SMAP[cur[1]]][SMAP[cur[2]]][SMAP[cur[3]]] + 1; | |
q.add(no); | |
} | |
} | |
} | |
} | |
return d; | |
} | |
// 要素数5の集合についてテーブルを作成 | |
static byte[][][][][] simulate5(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[5]; | |
int oc = 0; | |
for(int i = 0;i < 5;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
oc |= o[i]<<(6*i); | |
} | |
byte[][][][][] d = new byte[SP][SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
for(int l = 0;l < SP;l++){ | |
Arrays.fill(d[i][j][k][l], (byte)255); | |
} | |
} | |
} | |
} | |
Queue<Integer> q = new ArrayDeque<Integer>(); | |
q.add(oc); | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]][SMAP[o[4]]] = 0; | |
int[] curo = new int[5]; | |
while(!q.isEmpty()){ | |
int cur = q.poll(); | |
long hit = 0; | |
for(int i = 0;i < 5;i++){ | |
curo[i] = cur>>6*i&63; | |
hit |= 1L<<curo[i]; | |
} | |
byte curd = d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]]; | |
for(int l = 0;l < 5;l++){ | |
int nya = curo[l]; | |
cur ^= curo[l]<<6*l; | |
for(int[] nei : NEIS[nya]){ | |
if(hit<<63-nei[0]<0)continue; | |
curo[l] = nei[0]; | |
if(d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] == -1){ | |
d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]] = (byte)(curd + 1); | |
q.add(cur^(curo[l]<<6*l)); | |
} | |
} | |
curo[l] = nya; | |
cur ^= curo[l]<<6*l; | |
} | |
} | |
return d; | |
} | |
// 要素数6の集合についてテーブルを作成 | |
// not verified | |
static byte[][][][][][] simulate6(int h, int w, long obs, long ptn) | |
{ | |
int[] o = new int[6]; | |
long oc = 0; | |
for(int i = 0;i < 6;i++,ptn&=ptn-1){ | |
o[i] = Long.numberOfTrailingZeros(ptn); | |
oc |= o[i]<<(6*i); | |
} | |
byte[][][][][][] d = new byte[SP][SP][SP][SP][SP][SP]; | |
for(int i = 0;i < SP;i++){ | |
for(int j = 0;j < SP;j++){ | |
for(int k = 0;k < SP;k++){ | |
for(int l = 0;l < SP;l++){ | |
for(int m = 0;m < SP;m++){ | |
Arrays.fill(d[i][j][k][l][m], (byte)255); | |
} | |
} | |
} | |
} | |
} | |
Queue<Long> q = new ArrayDeque<Long>(); | |
q.add(oc); | |
d[SMAP[o[0]]][SMAP[o[1]]][SMAP[o[2]]][SMAP[o[3]]][SMAP[o[4]]][SMAP[o[5]]] = 0; | |
int[] curo = new int[5]; | |
while(!q.isEmpty()){ | |
long cur = q.poll(); | |
long hit = 0; | |
for(int i = 0;i < 6;i++){ | |
curo[i] = (int)(cur>>6*i&63); | |
hit |= 1L<<curo[i]; | |
} | |
byte curd = d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]][SMAP[curo[5]]]; | |
for(int l = 0;l < 5;l++){ | |
int nya = curo[l]; | |
cur ^= curo[l]<<6*l; | |
for(int[] nei : NEIS[nya]){ | |
if(hit<<63-nei[0]<0)continue; | |
curo[l] = nei[0]; | |
if(d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]][SMAP[curo[5]]] == -1){ | |
d[SMAP[curo[0]]][SMAP[curo[1]]][SMAP[curo[2]]][SMAP[curo[3]]][SMAP[curo[4]]][SMAP[curo[5]]] = (byte)(curd + 1); | |
q.add(cur^curo[l]<<6*l); | |
} | |
} | |
cur ^= curo[l]<<6*l; | |
curo[l] = nya; | |
} | |
} | |
return d; | |
} | |
// 盤面の最適分割を乱択で計算 | |
static long[] split(int N, int M, long obs, int D) | |
{ | |
long[] opt = null; | |
Random gen = new Random(); | |
int left = N*M-Long.bitCount(obs) - D; | |
long mask = (1L<<N*M)-1; | |
long lmask = 0; | |
long rmask = 0; | |
for(int i = 0;i < N;i++){ | |
lmask |= 1L<<i*M; | |
rmask |= 1L<<i*M+M-1; | |
} | |
lmask = ~lmask; | |
rmask = ~rmask; | |
long S = System.currentTimeMillis(); | |
int maxconn = 0; | |
outer: | |
for(int o = 0;o < 100000;o++){ | |
long[] b = new long[D]; | |
long all = obs; | |
for(int i = 0;i < D;i++){ | |
int pos = -1; | |
do{ | |
pos = gen.nextInt(N*M); | |
}while(all<<63-pos<0); | |
b[i] |= 1L<<pos; | |
all |= 1L<<pos; | |
} | |
for(int i = 0;i < left;i++){ | |
int c = i % D; | |
long nei = (b[c]<<M|b[c]>>M|(b[c]&lmask)>>1|(b[c]&rmask)<<1)&~all&mask; | |
if(nei == 0)continue outer; | |
int q = gen.nextInt(Long.bitCount(nei)); | |
for(int j = 1;j <= q;j++, nei&=nei-1); | |
long chosen = nei&-nei; | |
b[c] |= chosen; | |
all |= chosen; | |
} | |
int conn = 0; | |
for(int i = 0;i < D;i++){ | |
conn += Long.bitCount((b[i]<<M)&b[i]); | |
conn += Long.bitCount((b[i]>>M)&b[i]); | |
conn += Long.bitCount(((b[i]&lmask)>>1)&b[i]); | |
conn += Long.bitCount(((b[i]&rmask)<<1)&b[i]); | |
} | |
if(conn > maxconn){ | |
maxconn = conn; | |
opt = Arrays.copyOf(b, D); | |
} | |
} | |
long G = System.currentTimeMillis(); | |