Skip to content

Instantly share code, notes, and snippets.

@uwi

uwi/FCount.java

Created September 12, 2011 15:45
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save uwi/1211596 to your computer and use it in GitHub Desktop.
Save uwi/1211596 to your computer and use it in GitHub Desktop.
Download ZIP
GDD2011 DevQuiz スライドパズル用
Raw
FCount.java
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)); }
}
Raw
FDFS4.java
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)); }
}
Raw
FDFS4MCMC.java
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)); }
}
Raw
FIDA.java
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)); }
}
Raw
FIDA2.java
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)); }
}
Raw
FIDAM2.java
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();
if(opt != null){
char[][] SP = 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){
SP[i][j] = '#';
continue;
}
for(int k = 0;k < D;k++){
if(opt[k]<<63-q<0){
SP[i][j] = (char)('A'+k);
break;
}
}
}
}
for(char[] row : SP){
tr(row);
}
}
tr(G-S+"ms");
return opt;
}
// 評価値計算
static int dist(long[] v, int h, int w)
{
int ret = 0;
int hw = h*w;
int[] ipos = new int[hw];
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;
}
}
try {
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]];
}
if(l == 5){
RAFS[i].seek((((SMAP[x[1]]*SP+SMAP[x[2]])*SP+SMAP[x[3]])*SP+SMAP[x[4]])*SP+SMAP[x[5]]);
ret += RAFS[i].read();
}else if(l == 6){
RAFS[i].seek(((((SMAP[x[0]]*SP+SMAP[x[1]])*SP+SMAP[x[2]])*SP+SMAP[x[3]])*SP+SMAP[x[4]])*SP+SMAP[x[5]]);
ret += RAFS[i].read();
}else{
ret += ST[i][SMAP[x[2]]][SMAP[x[3]]][SMAP[x[4]]][SMAP[x[5]]];
}
}
} catch (IOException e) {
e.printStackTrace();
}
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)); }
}
Raw
FMerge.java
package gdd2011;
import java.io.File;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
/**
* 出力結果のマージ
* @author uwi
*
*/
public class FMerge {
static Scanner in, in2;
static PrintWriter out;
static int[] ch = new int[4];
static void solve()
{
int ct = 0, ct2 = 0, ctn = 0;
for(int o = 0;o < 5000;o++){
String line = in.nextLine();
String line2 = in2.hasNextLine() ? in2.nextLine() : "";
if(line.length() > 0)ct++;
if(line2.length() > 0)ct2++;
if(line.length() > 0 || line2.length() > 0)ctn++;
if(line.length() == 0){
out.println(line2);
count(line2);
}else if(line2.length() == 0){
out.println(line);
count(line);
}else if(line.length() != line2.length()){
if(line.length() < line2.length()){
out.println(line);
count(line);
}else{
out.println(line2);
count(line2);
}
}else{
if(line.equals(line2)){
// tr("equal!", line);
}else{
tr("collapse!", line, line2);
}
out.println(line);
count(line);
}
}
tr(ct, ct2, ctn);
tr(ch);
}
static void count(String x)
{
for(int i = 0;i < x.length();i++){
ch["LRUD".indexOf(x.charAt(i))]++;
}
}
public static void main(String[] args) throws Exception
{
long s = System.currentTimeMillis();
in = new Scanner(new File("x:\\outputFinal912C.txt"));
in2 = new Scanner(new File("x:\\output09120339.txt"));
out = new PrintWriter("x:\\outputFinal912D.txt");
solve();
out.flush();
tr(System.currentTimeMillis() - s+"ms");
}
static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Raw
FSIM.java
package gdd2011;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
/**
* 手シミュレーション用
* @author uwi
*
*/
public class FSIM {
static Scanner in;
static PrintWriter out;
static String INPUT = "6,4,E3456C2D1==0KJNF9H87==GI\r\nULLLLDLDRRRRRUULLLLDRULDRDRRRUULLLLDRDLLUURRRRRDDLLLLLUURRRRRDDLLLUU";
// static String INPUT = "6,6,=74638EF9==C2KDGHI50====J=RSTUPVWXYZ\r\nURULLDDRURULURRRRDDLLLUURRRDDLLLLUURRRRDDLLLLUURDLLDRULDRRULLDRRRRRUULLLDLDRRRRUULLLDLLDR" + "DLURRULLDDRULURDRRRRUULLLDLDRULURDDLDLDDRRRRR";
// static String INPUT = "6,6,=74638EF9==C2KDGHI50====J=RSTUPVWXYZ\r\nURULLDDRURULURRRRDDLLLUURRRDDLLLLUURRRRDDLLLLUURDLLDRULDRRULL";
// static String INPUT = "6,6,=93450K72==6VPF8=NDJ=GMCXE===IWQYZUO\r\nLLLDDLDDDRRRRUUUUULLLDDRDRRDDLLLLLURDLUUUURRURRRDDDDDLLLLULUURUURRRRDDDDDLLLLLURUUURDLURDL" + "LDDRULURDLDRULURDDD" + "RRRR";
// static String INPUT = "6,6,40G9E31DJA56872F=BP===NZVWR=CUXQYTOI\r\n" +
// "LDDDDRDRRRRUULDDRUULDDLLLLUUURRURRRDDLDDLLLLUUURRRURRDDDLURDLURUU" +
// "LLLLLDDDDRRRRUURUU" + "LLDLULLD" + "RRUURRRDL" + "LLURDDLUURDLDRUULDDRUURDRDDLDDLLLLUUURRRU"
// + "ULLDRRULDR" // 2*4
// + "RRDDLDDR";
// static String INPUT = "6,4,9N10567=42IHEK=A3BJDLGMC\r\nLLLDDDRRRUUULLLDDDRRRRUURULLDLURDDRUULDDRDLURULDDLLLUUURRRDDDLLULUURRRRRDDDLLLLULDRRR" + "RRULULDDRURDLUURDD"; // 4563
// static String INPUT = "6,6,1DF35C742G6B98E0H=KQ=AMZJPRSUNVWXYTO\r\n" +
// "LLURULDDRULDRRULURDLURRDRULLLD";
// static String INPUT = "6,6,=74638EF9==C2KDGHI50====J=RSTUPVWXYZ\r\n" + // 4789
// "LUURURRRRDDLLLUURRRDDLLLLUURRRRDDLLLLUURDLDDLUURDRULDRRRRUULLLDDRRRUULLLLDLDRRUULDDLURDRUULDDRRRRUULLLLDDDLUURDRRRRUULLLLDRURRRDDLLL" + "LLURRDLLDRULURRDLLURDDLUURDDL" + "DDRRRRR";
// static String INPUT = "6,6,=93450K72==6VPF8=NDJ=GMCXE===IWQYZUO\r\n" +
// "LLLDDRDRRUUULLLDDRDRRDDLLLLUUURRDRRDDLLLLUUURRDRRDDLLLLUUURRDRRDDLLLLLUUUURRDLDDDRRRRUULLULLDDDRRRRUULLULLDDDRRRRUULLULLDDDRRRRUULLULLUURRRRDDDDDLLLLUUUUURRRRDDD" +
// "DDLLLLLUUURRRDRR" + "DDLLLLLUUURRRDRR" + "DDLLLLLUUURRRDRR" + "DDLLLLLUUURRU" + "LLDDDDRRRRRUULLULL" + "DDDRRRRUULLULLLURDLURRDLULDDDDRRRRRUULLULL" + "ULDDDDRRRRRUULLUL" + "ULLDDRU" + "LDDRU" + "LDRDRRRRUULLU" + "LLDDDLUU" + "RURRDRRDDLLLLL" + "UUUURRDRDRRDDLLLLL"
// + "RULUURDLUURRDLDDLUUURDRULLDRDDLURDDRRRR";
// rev LURUULDRUULLDRDDRUUULDLURRDLDDRULDDR
// static String INPUT = "6,5,438C5I12=GLA7=Q6OMD=PRHBJ0SFNT\r\n" + // 1935
// "LUUURURRDDDDLLLUUURULDDDDRRUURUULLLDDDDRRUURUULLLDDDDRRU" + "RRURULLDRRUULDDRDLLURDLULDRRULURDRULURDLDDDR";
static int[] dr = {1, 0, -1, 0};
static int[] dc = {0, 1, 0, -1};
static void solve()
{
int h, w;
String line = in.nextLine();
String[] sp = line.split(",");
w = Integer.parseInt(sp[0]);
h = Integer.parseInt(sp[1]);
char[] u = sp[2].toCharArray();
tr(INPUT);
// 数値盤面作成
char[][] b = new char[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] = u[j*w+k];
if(b[j][k] != '=')alive++;
if(b[j][k] == '0'){
zr = j; zc = k;
}
if(b[j][k] == '='){
obs |= 1L<<j*w+k;
}
}
}
print(b);
char[] op = in.nextLine().toCharArray();
int step = 0;
for(char c : op){
int k = "DRUL".indexOf(c);
if(k == -1){
tr("invalid operation", step);
break;
}
int nr = zr + dr[k], nc = zc + dc[k];
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){
b[zr][zc] = b[nr][nc];
b[nr][nc] = '0';
zr = nr; zc = nc;
}else{
tr("dead!", step);
}
step++;
}
print(b);
}
static void print(char[][] b)
{
for(int i = 0;i < b.length;i++){
tr(new String(b[i]));
}
tr();
}
// 入力文字を数値に変換
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
{
in = new Scanner(INPUT);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
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)); }
}
Raw
FSIM2.java
package gdd2011;
import java.io.File;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* 正解確認用
* @author uwi
*
*/
public class FSIM2 {
static Scanner in, in2;
static PrintWriter out;
static int[] dr = {1, 0, -1, 0};
static int[] dc = {0, 1, 0, -1};
static void solve()
{
ni();ni();ni();ni();ni();in.nextLine();
outer:
for(int o = 0;o < 5000;o++){
int h, w;
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;
}
}
}
char[] op = in2.nextLine().toCharArray();
int step = 0;
Map<Long, Integer> encs = new HashMap<Long, Integer>();
encs.put(enc(b), step);
for(char c : op){
step++;
int k = "DRUL".indexOf(c);
if(k == -1){
tr(o, "invalid operation", step);
continue outer;
}
int nr = zr + dr[k], nc = zc + dc[k];
if(nr >= 0 && nr < h && nc >= 0 && nc < w && obs<<63-(nr*w+nc)>=0){
b[zr][zc] = b[nr][nc];
b[nr][nc] = 0;
zr = nr; zc = nc;
}else{
tr(o, "dead!", step);
continue outer;
}
if(encs.containsKey(enc(b))){
tr(o, "duplicate " + step + "&" + encs.get(enc(b)));
// continue outer;
}
encs.put(enc(b), step);
}
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
if(b[i][j] == i*w+j+1 || b[i][j] <= 0){
}else{
tr(o, "final dead!", i, j);
print(b);
continue outer;
}
}
}
}
}
static void print(int[][] b)
{
for(int i = 0;i < b.length;i++){
tr(b[i]);
}
tr();
}
// 入力文字を数値に変換
static int dec(char x)
{
if(x == '=')return -1;
if(x >= '0' && x <= '9')return x - '0';
return x - 'A' + 10;
}
static long enc(int[][] b)
{
int h = b.length;
int w = b[0].length;
int p = 37;
long ret = 0;
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
ret = ret * p + b[i][j];
}
}
return ret;
}
public static void main(String[] args) throws Exception
{
in = new Scanner(new File("x:\\input.txt"));
in2 = new Scanner(new File("x:\\output.txt"));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
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)); }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment