基本、双方向幅優先で物理パワーでねじ伏せる作戦。
優先して残すのは、ゴールまでのマンハッタン距離が近いもの。
以下のコードで-Xmx4608M付けてXeonの6G、64ビットUbuntu10.10マシンで40時間かけると4872問解けます(残り128)。
更に残ったものについて、幅増やしたり上限増やしたりして残り49。
さらに、最初の10手はスタートからの遠さ優先その後ゴールまでの近さ優先、次最初の20手は...と繰り返して行って、残り14。あとは手動で小さいサイズの問題に帰着させて解かせた。
一番原始的な気がする。
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Hashtable;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Enumeration;
public class Panel2 {
public static final int MAX_NUM = 10000;
public static final int MAX_COUNT = 100;
public class InnerPanel {
int width, height;
char maxc;
int maxcount;
String panel[];
int distance;
int zerox, zeroy;
StringBuffer route;
/**
* コンストラクタ(初期状態用).
*/
public InnerPanel(int width, int height, String panelstr) {
// 幅高さ
this.width = width;
this.height = height;
// 配列化
panel = new String[height];
for (int i = 0; i < height; i++)
panel[i] = panelstr.substring(width * i, width * (i + 1));
// 一番でかい文字保存＆0位置保存
maxc = '0';
char c;
for (int i = 0; i < panelstr.length(); i++) {
c = panelstr.charAt(i);
if (c == '=')
continue;
if (c == '0') {
zeroy = i / width;
zerox = i % width;
}
if (maxc < c)
maxc = c;
}
maxcount = toInt(maxc);
route = new StringBuffer();
}
/**
* コンストラクタ(ゴール作成用).
*/
private InnerPanel(int width, int height) {
// 幅高さ
this.width = width;
this.height = height;
this.route = new StringBuffer();
}
/**
* ゴール作成.
*/
public InnerPanel makeGoal() {
InnerPanel goal = new InnerPanel(width, height);
goal.maxc = maxc;
goal.maxcount = maxcount;
// 整列した状態作成
goal.panel = new String[height];
int count = 0;
String line = null;
char c;
for (int i = 0; i < height; i++) {
line = panel[i];
StringBuffer sb = new StringBuffer();
for (int j = 0; j < width; j++) {
count++;
c = line.charAt(j);
if (c == '=') {
sb.append(c);
} else if (count > maxcount) {
sb.append('0');
goal.zeroy = i;
goal.zerox = j;
} else {
sb.append(toChar(count));
}
}
goal.panel[i] = sb.toString();
}
return goal;
}
/**
* 文字から数値へ.
*/
public int toInt(char c) {
if ('0' <= c && c <= '9')
return c - '0';
else
return c - 'A' + 10;
}
/**
* 数値から文字へ.
*/
public char toChar(int i) {
if (i < 10)
return (char)('0' + i);
else
return (char)('A' + i - 10);
}
/**
* パネル内容の表示.
*/
public void print() {
System.out.println("======");
for (int i = 0; i < panel.length; i++)
System.out.println(panel[i]);
}
public int getDistance(InnerPanel target) {
String p1[] = panel;
String p2[] = target.panel;
// 文字->座標のHashtable作成
Hashtable<Character, Integer> p1hash =
new Hashtable<Character, Integer>();
Hashtable<Character, Integer> p2hash =
new Hashtable<Character, Integer>();
String p1line = null, p2line = null;
char c1, c2;
for (int i = 0; i < p1.length; i++) {
p1line = p1[i];
p2line = p2[i];
for (int j = 0; j < p1line.length(); j++) {
c1 = p1line.charAt(j);
if (c1 != '=' && c1 != '0') {
p1hash.put(c1, i * 10 + j);
}
c2 = p2line.charAt(j);
if (c2 != '=' && c2 != '0')
p2hash.put(c2, i * 10 + j);
}
}
char c;
Integer xy1, xy2;
int sa, total = 0;
for (int i = 1; i <= maxcount; i++) {
c = toChar(i);
xy1 = p1hash.get(c);
if (xy1 == null)
continue;
xy2 = p2hash.get(c);
sa = Math.abs(xy1 / 10 - xy2 / 10) +
Math.abs(xy1 % 10 - xy2 % 10);
total += sa;
}
return total;
}
/**
* 距離を計算して保存.
*/
public int calculateDistance(InnerPanel target) {
distance = getDistance(target);
return distance;
}
/**
* String表現.
*/
public String toString() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < height; i++)
sb.append(panel[i]);
return sb.toString();
}
/**
* 次の状態.
*/
public InnerPanel[] nextPanels() {
ArrayList<InnerPanel> panel_array = new ArrayList<InnerPanel>();
char up = 0, down = 0, left = 0, right = 0;
if (zeroy > 0)
up = panel[zeroy - 1].charAt(zerox);
if (zeroy < height - 1)
down = panel[zeroy + 1].charAt(zerox);
if (zerox > 0)
left = panel[zeroy].charAt(zerox - 1);
if (zerox < width - 1)
right = panel[zeroy].charAt(zerox + 1);
try {
if (up != 0 && up != '=')
panel_array.add(makeUp());
if (down != 0 && down != '=')
panel_array.add(makeDown());
if (left != 0 && left != '=')
panel_array.add(makeLeft());
if (right != 0 && right != '=')
panel_array.add(makeRight());
} catch (IOException ex) {
;
}
return (InnerPanel[])panel_array.toArray(new InnerPanel[0]);
}
/**
* コピー作成.
*/
public InnerPanel makeCopy() {
InnerPanel copy = new InnerPanel(width, height);
copy.maxc = maxc;
copy.maxcount = maxcount;
copy.panel = new String[panel.length];
for (int i = 0; i < panel.length; i++)
copy.panel[i] = panel[i];
copy.distance = distance;
copy.zerox = zerox;
copy.zeroy = zeroy;
copy.route = new StringBuffer(route.toString());
return copy;
}
/**
* 上へ移動.
*/
public InnerPanel makeUp() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy - 1].getBytes("UTF-8");
byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = sline[zerox];
sline[zerox] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy - 1] = new String(tline, "UTF-8");
copy.panel[zeroy] = new String(sline, "UTF-8");
copy.zeroy--;
copy.route.append('U');
return copy;
}
/**
* 下へ移動.
*/
public InnerPanel makeDown() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy + 1].getBytes("UTF-8");
byte sline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = sline[zerox];
sline[zerox] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy + 1] = new String(tline, "UTF-8");
copy.panel[zeroy] = new String(sline, "UTF-8");
copy.zeroy++;
copy.route.append('D');
return copy;
}
/**
* 左へ移動.
*/
public InnerPanel makeLeft() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = tline[zerox - 1];
tline[zerox - 1] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy] = new String(tline, "UTF-8");
copy.zerox--;
copy.route.append('L');
return copy;
}
/**
* 右へ移動.
*/
public InnerPanel makeRight() throws IOException {
InnerPanel copy = makeCopy();
byte tline[] = copy.panel[zeroy].getBytes("UTF-8");
byte b = tline[zerox + 1];
tline[zerox + 1] = tline[zerox];
tline[zerox] = b;
copy.panel[zeroy] = new String(tline, "UTF-8");
copy.zerox++;
copy.route.append('R');
return copy;
}
}
/**
* メイン.
*/
public static void main(String args[]) {
int skip = 0;
if (args.length > 0)
skip = Integer.parseInt(args[0]);
try {
InputStreamReader isr = null;
try {
isr = new InputStreamReader(System.in, "UTF-8");
BufferedReader br = null;
try {
br = new BufferedReader(isr);
new Panel2().play(br, skip);
} finally {
if (br != null) br.close();
}
} finally {
if (isr != null) isr.close();
}
} catch (IOException ex) {
ex.printStackTrace();
System.exit(1);
}
System.exit(0);
}
public int lx = 0;
public int rx = 0;
public int ux = 0;
public int dx = 0;
public int cases = 0;
/**
* コンストラクタ.
*/
public Panel2() {
}
/**
* 開始.
*/
public void play(BufferedReader br, int skip) throws IOException {
String numberstr = br.readLine();
String numbers[] = numberstr.split(" ");
lx = Integer.parseInt(numbers[0]);
rx = Integer.parseInt(numbers[1]);
ux = Integer.parseInt(numbers[2]);
dx = Integer.parseInt(numbers[3]);
cases = Integer.parseInt(br.readLine());
for (int i = 0; i < skip; i++)
br.readLine();
for (int i = 0; i < cases; i++) {
solve(skip + i + 1, br.readLine());
}
}
/**
* 1問解く.
*/
public void solve(int panel_num, String line) {
String lines[] = line.split(",");
int width = Integer.parseInt(lines[0]);
int height = Integer.parseInt(lines[1]);
InnerPanel start_panel = new InnerPanel(width, height, lines[2]);
InnerPanel goal_panel = start_panel.makeGoal();
Hashtable<String, String> route_hash = new Hashtable<String, String>();
// 距離設定
start_panel.calculateDistance(goal_panel);
goal_panel.calculateDistance(start_panel);
// 既出状態保存
Hashtable<String, InnerPanel> start_already_hash = new Hashtable<String, InnerPanel>();
Hashtable<String, InnerPanel> goal_already_hash = new Hashtable<String, InnerPanel>();
// 先端状態保存
ArrayList<InnerPanel> start_edge_array = new ArrayList<InnerPanel>();
Hashtable<String, InnerPanel> start_edge_hash =
new Hashtable<String, InnerPanel>();
ArrayList<InnerPanel> start_next_array = new ArrayList<InnerPanel>();
ArrayList<InnerPanel> goal_edge_array = new ArrayList<InnerPanel>();
Hashtable<String, InnerPanel> goal_edge_hash =
new Hashtable<String, InnerPanel>();
ArrayList<InnerPanel> goal_next_array = new ArrayList<InnerPanel>();
// 初期状態にする
start_edge_array.add(start_panel);
start_edge_hash.put(start_panel.toString(), start_panel);
start_already_hash.put(start_panel.toString(), start_panel);
goal_edge_array.add(goal_panel);
goal_edge_hash.put(goal_panel.toString(), goal_panel);
goal_already_hash.put(goal_panel.toString(), goal_panel);
// ここからぶんまわす
InnerPanel onePanel, newPanel, newPanels[], bingo;
String sum = null;
boolean bingo_flg = false;
int loop_count = 0;
while (true) {
++loop_count;
if (loop_count > MAX_COUNT) {
System.out.println(panel_num + ":");
break;
}
// ゴール側からの比較用Hashtableクリア
start_edge_hash = new Hashtable<String, InnerPanel>();
start_next_array = new ArrayList<InnerPanel>();
// スタート状態からの先端状態モノでループ
for (int i = 0; i < start_edge_array.size(); i++) {
onePanel = start_edge_array.get(i);
// 次の状態取得
newPanels = onePanel.nextPanels();
for (int j = 0; j < newPanels.length; j++) {
newPanel = newPanels[j];
sum = newPanel.toString();
// 既出なら捨てる
if (start_already_hash.containsKey(sum))
continue;
// 追加
start_already_hash.put(sum, newPanel);
// 既出とビンゴ？
bingo = goal_already_hash.get(sum);
if (bingo != null) {
checkMate(newPanel, bingo, true, panel_num, route_hash);
bingo_flg = true;
}
// ビンゴ？
bingo = goal_edge_hash.get(sum);
if (bingo != null) {
checkMate(newPanel, bingo, true, panel_num, route_hash);
bingo_flg = true;
}
// 既出じゃなければゴールとの距離計算
newPanel.calculateDistance(goal_panel);
if (newPanel.distance == 0) {
checkMate(newPanel, null, true, panel_num, route_hash);
bingo_flg = true;
}
// 次の先端状態モノに入れる
start_next_array.add(newPanel);
start_edge_hash.put(sum, newPanel);
}
}
start_edge_array = sort(start_next_array);
// スタート側からのがビンゴ
if (bingo_flg)
break;
// スタート側からの比較用Hashtableクリア
goal_edge_hash = new Hashtable<String, InnerPanel>();
goal_next_array = new ArrayList<InnerPanel>();
// ゴール側からの先端状態モノでループ
for (int i = 0; i < goal_edge_array.size(); i++) {
onePanel = goal_edge_array.get(i);
// 次の状態取得
newPanels = onePanel.nextPanels();
for (int j = 0; j < newPanels.length; j++) {
newPanel = newPanels[j];
sum = newPanel.toString();
// 既出なら捨てる
if (goal_already_hash.containsKey(sum))
continue;
// 追加
goal_already_hash.put(sum, newPanel);
// 既出とビンゴ？
bingo = start_already_hash.get(sum);
if (bingo != null) {
checkMate(bingo, newPanel, false, panel_num, route_hash);
bingo_flg = true;
}
// ビンゴ？
bingo = start_edge_hash.get(sum);
if (bingo != null) {
checkMate(bingo, newPanel, false, panel_num, route_hash);
bingo_flg = true;
}
// 既出じゃなければ初期との距離計算
newPanel.calculateDistance(start_panel);
if (newPanel.distance == 0) {
checkMate(null, newPanel, true, panel_num, route_hash);
bingo_flg = true;
}
// 次の先端状態モノに入れる
goal_next_array.add(newPanel);
goal_edge_hash.put(sum, newPanel);
}
}
goal_edge_array = sort(goal_next_array);
// ゴール側からのがビンゴ
if (bingo_flg)
break;
}
Enumeration<String> e = route_hash.keys();
while (e.hasMoreElements()) {
String key = e.nextElement();
System.out.println(panel_num + ":" + route_hash.get(key) + ":" + key);
}
}
public ArrayList<InnerPanel> sort(ArrayList<InnerPanel> source) {
InnerPanel source_array[] = source.toArray(new InnerPanel[0]);
Arrays.sort(source_array, new PanelCompare());
ArrayList<InnerPanel> sorted_list = new ArrayList<InnerPanel>();
for (int i = 0; i < MAX_NUM && i < source_array.length; i++)
sorted_list.add(source_array[i]);
return sorted_list;
}
public class PanelCompare implements Comparator {
public int compare(Object o1, Object o2) {
InnerPanel p1 = (InnerPanel)o1;
InnerPanel p2 = (InnerPanel)o2;
return p1.distance - p2.distance;
}
}
/**
* チェックメイト.
*/
public void checkMate(InnerPanel start_side, InnerPanel goal_side,
boolean even, int panel_num, Hashtable<String, String> route_hash) {
StringBuffer resolv_sb = null;
if (start_side != null)
resolv_sb = new StringBuffer(start_side.route.toString());
else
resolv_sb = new StringBuffer();
StringBuffer goal_sb = null;
if (goal_side != null)
goal_sb = goal_side.route;
else
goal_sb = new StringBuffer();
char c;
for (int i = goal_sb.length() - 1; i >= 0; i--) {
c = goal_sb.charAt(i);
switch (c) {
case 'U':
resolv_sb.append('D');
break;
case 'D':
resolv_sb.append('U');
break;
case 'L':
resolv_sb.append('R');
break;
case 'R':
resolv_sb.append('L');
break;
}
}
String result = resolv_sb.toString();
// カウント
int u_count = 0, d_count = 0, l_count = 0, r_count = 0;
for (int i = 0; i < result.length(); i++) {
c = result.charAt(i);
switch (c) {
case 'U':
u_count++;
break;
case 'D':
d_count++;
break;
case 'L':
l_count++;
break;
case 'R':
r_count++;
break;
}
}
StringBuffer save_sb = new StringBuffer();
save_sb.append("U=");
save_sb.append(u_count);
save_sb.append(",D=");
save_sb.append(d_count);
save_sb.append(",L=");
save_sb.append(l_count);
save_sb.append(",R=");
save_sb.append(r_count);
route_hash.put(save_sb.toString(), result);
}
}
0 件のコメント:
コメントを投稿