[[07年度-ACM-ICPC国内予選]]&br;
&br;
追記：データセットが公開されましたので、実行してみました。&br;
&br;
&br;
***[[2007D:http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2007/contest/D_ja.html]] [#x8c8b421]
-''Blue Screenの解答''
予選時：未回答
-回答者：[[ゆん]]
-所要時間：凄くたくさん
-予選時：未回答
まだ未確定の部分を距離の短い方から順に確定していく。ダイクストラ法もどき。
途中で壁にぶつかってコードを一から書き直したので、とんでもなく時間を使ってしまった。最後にどうしても値が合わなかったのだが、forのループ回数を間違えるという単純なミスだったことが発覚して脱力。
愉快なほどのスパゲッティコードです。デバッグプリントが散在。
実行時間は意外と速いです。サンプルぐらいなら一瞬。
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Climber2007D {
public static int w, h;
public static final int[][] src = new int[30][60], left = new int[30][60], right = new int[30][60];
public final static UniqueDynamicSortedList l = new UniqueDynamicSortedList();
/**
* @param args
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(new File("sample.txt"));
while(true) {
w = sc.nextInt();
h = sc.nextInt();
if(w == 0 && h == 0) break;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if(sc.hasNextInt())
src[j][i] = sc.nextInt();
else if(sc.hasNext()){
String c = sc.next();
if(c.equals("X"))
src[j][i] = -1;
if(c.equals("S"))
src[j][i] = 0;
if(c.equals("T"))
src[j][i] = 0;
}
}
}
for (int i = 0; i < h; i++) {
if(i < h - 1) {
for (int j = 0; j < w; j++) {
left[j][i] = Integer.MAX_VALUE;
}
} else {
for (int j = 0; j < w; j++) {
if(src[j][i] == 0)
left[j][i] = 0;
else
left[j][i] = Integer.MAX_VALUE;
}
}
}
for (int i = 0; i < h; i++) {
if(i < h - 1) {
for (int j = 0; j < w; j++) {
right[j][i] = Integer.MAX_VALUE;
}
} else {
for (int j = 0; j < w; j++) {
if(src[j][i] == 0)
right[j][i] = 0;
else
right[j][i] = Integer.MAX_VALUE;
}
}
}
for(int i = 0; i <w; i++) {
if(src[i][h - 1] == 0){
l.add(new Step(i, h - 1, Step.LEFT));
l.add(new Step(i, h - 1, Step.RIGHT));
}
}
Step s;
while((s = l.pop()) != null) {
s.next();
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < w; i++) {
if(src[i][0] == 0){
min = min < left[i][0] ? min : left[i][0];
min = min < right[i][0] ? min : right[i][0];
}
}
if(min != Integer.MAX_VALUE)
System.out.println(min);
else
System.out.println(-1);
// printArray(src);
// printArray(left);
// printArray(right);
}
}
public static void printArray(int[][] arr){
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
int k = arr[j][i];
if(k != Integer.MAX_VALUE)
System.out.print(k + " ");
else
System.out.print("∞ ");
}
System.out.println("");
}
System.out.println("");
}
}
class Step{
public final int x, y;
private boolean left;
public static final boolean LEFT = true, RIGHT = false;
/**
* @param x
* @param y
* @param lr
*/
public Step(final int x, final int y, boolean left) {
if(x < 0 || y < 0) throw new IllegalArgumentException(x + ", " + y);
if(x >= Climber2007D.w || y >= Climber2007D.h) throw new IllegalArgumentException(x + ", " + y);
this.x = x;
this.y = y;
this.left = left;
}
public boolean isLeft() {
return left;
}
@Override
public int hashCode() {
final int PRIME = 31;
int result = 1;
result = PRIME * result + (left ? 1231 : 1237);
result = PRIME * result + x;
result = PRIME * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Step other = (Step) obj;
if (left != other.left)
return false;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
public void next() {
// System.out.println("next: " + x + ", " + y + ", " + isLeft());
for (int i = -3; i <= 3; i++) {
for (int j = -3; j <= 3; j++) {
int tx = x + i;
int ty = y + j;
if(tx < 0 || tx >= Climber2007D.w || ty < 0 || ty >= Climber2007D.h) continue;
if(Math.abs(tx - x) + Math.abs(ty - y) > 3) continue;
if(Climber2007D.src[tx][ty] == -1) continue;
if(isLeft()){
if(tx <= x) continue;
if(Climber2007D.left[x][y] + Climber2007D.src[tx][ty] >= Climber2007D.right[tx][ty]) continue;
} else {
if(tx >= x) continue;
if(Climber2007D.right[x][y] + Climber2007D.src[tx][ty] >= Climber2007D.left[tx][ty]) continue;
}
step(tx, ty);
}
}
}
public void step(int tx, int ty) {
// System.out.println("step: " + tx + ", " + ty + ", " + !isLeft());
if(isLeft()){
Climber2007D.l.add(new Step(tx, ty, Step.RIGHT));
Climber2007D.right[tx][ty] = Climber2007D.src[tx][ty] + Climber2007D.left[x][y];
} else {
Climber2007D.l.add(new Step(tx, ty, Step.LEFT));
Climber2007D.left[tx][ty] = Climber2007D.src[tx][ty] + Climber2007D.right[x][y];
}
}
@Override
public String toString() {
if(isLeft())
return x + ", " + y + ", " + Climber2007D.left[x][y];
else
return x + ", " + y + ", " + Climber2007D.right[x][y];
}
}
class UniqueDynamicSortedList{
private List<Step> list = new ArrayList<Step>();
@SuppressWarnings("unchecked")
public boolean add(Step step) {
if(list.contains(step)) return false;
list.add(step);
// Collections.sort(list, new IllegalStepComparator());
return true;
}
@SuppressWarnings("unchecked")
public Step pop() {
if(list.isEmpty()) return null;
Collections.sort(list, new IllegalStepComparator());
Step step = list.get(0);
list.remove(0);
return step;
}
}
class IllegalStepComparator implements Comparator{
public int compare(Object arg0, Object arg1) {
Step s1 = (Step) arg0, s2 = (Step) arg1;
Integer first, second;
if(s1.isLeft()){
first = new Integer(Climber2007D.left[s1.x][s1.y]);
} else {
first = new Integer(Climber2007D.right[s1.x][s1.y]);
}
if(s2.isLeft()){
second = new Integer(Climber2007D.left[s2.x][s2.y]);
} else {
second = new Integer(Climber2007D.right[s2.x][s2.y]);
}
return first.compareTo(second);
}
}
-''include studioの解答''
回答者：[[ほへい]]&br;
所要時間：５時間くらい&br;
予選時：未回答&br;
&br;
言い訳：スタート時に両足が乗っているという条件でやっていました。&br;
&br;
変更：終了条件を一つ増やしたり、移動の順序を多少いじったりして高速化。&br;
サンプルインプットで１秒弱もたつきます&br;
&br;
備考：ゆんさんに倣ってダイクストラ法で解いてみたところ、この高速化をあざ笑うかのような速度が出ました。&br;
単なるダイクストラ法。特に何の工夫をしなくてもＯＫ。コード量も同程度。&br;
もしこの解法を推奨する問題なら、以下の５時間コードでは時間が足りないという悲劇に…。&br;
わりと泣けてきます。&br;
&br;
&br;
追記：やっぱり普通の解答は&color(red,){速度がまるで足りませんでした。};&br;
データセット１つで３時間以上。たぶん５時間くらいかかると思います。途中であきらめました。&br;
ダイクストラ法の方は、１つ１秒弱の速度で正解を確認。&br;
#include <stdio.h>
#include <stdlib.h>
FILE *fp_in, *fp_out;
enum {RIGHT = 0, LEFT = 1, GOAL, MOVABLE, UNMOVABLE, FALSE = 100000};
const char *f_source = "2007D_in.txt";
const char *f_answer = "2007D_out.txt";
typedef struct {
int x, y;
} Leg;
typedef struct {
char status;
int moved[2];
} Map;
typedef struct {
Map maps[60][30];
int width, height;
Leg legs[2];
int current_leg;
int answer;
} Status;
void setMap(Status*); // ファイルからマップ情報を読み取る
void getAnswer(Status); // 初期位置を決めて start を呼び出す
void markMoved(Status*); // 以降移動しないマスの情報を書き込む
int start(Status, Leg); // 踏みだし足に合わせて二回 allMove を呼び出す。小さい場合の値を返す
/* 移動可能な全ての場合で move 関数を呼び出す
返却値は move 関数の返却値のうち最も小さいもの */
int allMove(const Status*);
/* 渡された引数の位置に移動する。返却値は、ゴールならかかった時間。
移動可なら allMove を呼び出し、その返却値。移動不可ならFALSE */
int move(Status*, int x, int y);
/* 移動の可否の判定。
ゴールなら GOAL, 移動可能なら MOVABLE, それ以外には UNMOVABLE を返す */
int canMove(const Status*, int, int);
int limit; // その時点での最短ゴール時間を格納
int min[60][30][2]; // その時点で、ある地点に最短で移動できる時間を格納
int main(void)
{
Status first_status;
fp_in = fopen(f_source, "r");
fp_out = fopen(f_answer, "w");
while(1) {
fscanf(fp_in, "%d %d", &first_status.width, &first_status.height);
if(first_status.width == 0 && first_status.height == 0) break;
limit = FALSE;
setMap(&first_status);
getAnswer(first_status);
printf("end_dataset\n");
}
fclose(fp_in);
fclose(fp_out);
return 0;
}
void setMap(Status *status)
{
int i, j;
for(i = 0; i < status->height; i++) {
for( j = 0; j < status->width; j++) {
fscanf(fp_in, " %c", &status->maps[i][j].status);
status->maps[i][j].moved[LEFT] = 0;
status->maps[i][j].moved[RIGHT] = 0;
min[i][j][RIGHT] = FALSE;
min[i][j][LEFT] = FALSE;
}
}
status->answer = 0;
}
void getAnswer(Status status)
{
int i;
int temp, answer = FALSE;
for(i = 0; i < status.width; i++) {
if(status.maps[status.height - 1][i].status == 'S') {
Leg leg;
leg.x = i;
leg.y = status.height - 1;
temp = start(status, leg);
answer = (answer > temp) ? temp : answer;
}
}
if(answer == FALSE) answer = -1;
fprintf(fp_out, "%d\n", answer);
}
int start(Status status, Leg leg)
{
int temp, answer;
status.current_leg = RIGHT;
status.legs[LEFT] = leg;
answer = allMove(&status);
status.current_leg = LEFT;
status.legs[RIGHT] = leg;
temp = allMove(&status);
return ((temp > answer) ? answer : temp);
}
int allMove(const Status *status)
{
Status *t_status = (Status*)malloc(sizeof(Status));
int answer = FALSE, temp, another;
int i, j;
*t_status = *status;
another = (t_status->current_leg + 1) % 2;
for(i = 3; i > 0; i--) {
for(j = -3 + i; j < -i + 4; j++) {
if(another == RIGHT) {
Status *tt_status = (Status*)malloc(sizeof(Status));
*tt_status = *t_status;
temp = move(tt_status, tt_status->legs[another].x - i, tt_status->legs[another].y + j);
free(tt_status);
}
else if(another == LEFT) {
Status *tt_status = (Status*)malloc(sizeof(Status));
*tt_status = *t_status;
temp = move(tt_status, tt_status->legs[another].x + i, tt_status->legs[another].y + j);
free(tt_status);
}
answer = (answer > temp) ? temp : answer;
}
}
free(t_status);
return answer;
}
int canMove(const Status *status, int x, int y)
{
if(x >= 0 && x < status->width) {
if(y >= 0 && y < status->height) {
if(status->maps[y][x].status == 'T') {
return GOAL;
}
if(status->maps[y][x].status <= '9' && status->maps[y][x].status > '0') {
if(status->maps[y][x].moved[status->current_leg] == 0) {
int t_answer = status->answer + status->maps[y][x].status - '0';
if(min[y][x][status->current_leg] >= t_answer) {
min[y][x][status->current_leg] = t_answer;
return MOVABLE;
}
}
}
}
}
return UNMOVABLE;
}
int move(Status *status, int x, int y)
{
int flag = canMove(status, x, y);
if(flag == GOAL) {
limit = status->answer;
return status->answer;
}
else if(flag == MOVABLE) {
status->answer += status->maps[y][x].status - '0';
if(status->answer >= limit) {
return FALSE;
}
else {
markMoved(status);
status->legs[status->current_leg].x = x;
status->legs[status->current_leg].y = y;
status->current_leg = (status->current_leg + 1) % 2;
return allMove(status);
}
}
return FALSE;
}
void markMoved(Status *status)
{
int i, j;
int another = (status->current_leg + 1) % 2;
for(i = 1; i < 4; i++) {
for(j = -3 + i; j < -i + 4; j++) {
int x_index;
int y_index = status->legs[another].y + j;
if(another == RIGHT) {
x_index = status->legs[another].x - i;
}
else if(another == LEFT) {
x_index = status->legs[another].x + i;
}
if(x_index >= 0 && x_index < status->width) {
if(y_index >= 0 && y_index < status->height) {
status->maps[y_index][x_index].moved[status->current_leg] = -1;
}
}
}
}
}
解説&br;
&br;
終了条件は&br;
・一度でも移動可能だった場所には二度と同じ足を置かない。&br;
・一度でもゴールしたら、以降はその数値を超えた時点で再帰を抜ける。&br;
・より早くそのマスに足をおける場合（左右の区別は有り）があるなら、再帰を抜ける&br;
&br;
あとは再帰関数によるゴリ押しです。&br;
ちなみに、malloc でヒープ領域からメモリを確保しないと、スタック領域を食いつぶしてエラーがでるくらいメモリ喰いのプログラム。&br;
&br;
良い勉強になりました。&br;
&br;
&br;
追加：ダイクストラ法を用いて。&br;
Java版もありますし、コードが３つもあって邪魔そうなら削除します。&br;
[[ダイクストラ法の説明:http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_00.html]]
#include <stdio.h>
#include <stdlib.h>
enum {RIGHT = 0, LEFT, UNKNOWN = 100000};
FILE *fp_in, *fp_out;
const char *f_source = "2007D_in.txt";
const char *f_answer = "2007D_out.txt";
typedef struct {
int x, y, leg;
int correct_answer;
int temp_answer;
} Pannel;
typedef struct __P_Stack {
struct __P_Stack *prev, *next;
Pannel *pannel;
} P_Stack; // 確定したパネルのスタック
typedef struct {
int height, width;
char map[60][30];
Pannel pannels[60][30][2];
P_Stack start, end;
Pannel *min_temp;
} Status;
void setStatus(Status *status); // ファイルからマップを読み取る。
// 最短距離変数の初期化・スタート位置をスタックに積む。
void getAnswer(Status *status); // setTempAnswer・setMinPannelの呼び出し
void push(Status *status, Pannel *append); // append をスタックに積む。
void deletePannel(P_Stack *del_pStack); // del_pStack をスタックから削除
Pannel *pop(Status *status); // スタックからパネルポインタを取得
void setTempAnswer(Status *status, Pannel *pannel); // 仮の最短距離を更新する
void setMinPannel(Status *status); // 仮の最短距離が最も小さいものを見つける
int main(void)
{
Status status;
fp_in = fopen(f_source, "r");
fp_out = fopen(f_answer, "w");
while(1) {
fscanf(fp_in, "%d %d", &status.width, &status.height);
if(status.width == 0 && status.height == 0) break;
setStatus(&status);
getAnswer(&status);
}
fclose(fp_out);
fclose(fp_in);
return 0;
}
Pannel *pop(Status *status)
{
P_Stack *tempPStack;
Pannel *temp_pannel;
if(status->end.prev == &status->start) {
return NULL;
}
tempPStack = status->end.prev;
temp_pannel = tempPStack->pannel;
((status->end.prev)->prev)->next = &status->end;
status->end.prev = (status->end.prev)->prev;
deletePannel(tempPStack);
return temp_pannel;
}
void push(Status *status, Pannel *append)
{
if(append != NULL) {
P_Stack *pStack = (P_Stack*)malloc(sizeof(P_Stack));
pStack->next = &status->end;
pStack->prev = (status->end).prev;
(status->end.prev)->next = pStack;
(status->end).prev = pStack;
pStack->pannel = append;
}
}
void deletePannel(P_Stack *del_pStack)
{
free(del_pStack);
}
void setStatus(Status *status)
{
int i, j, k;
status->start.next = &status->end;
status->end.prev = &status->start;
for(i = 0; i < status->height; i++) {
for(j = 0; j < status->width; j++) {
fscanf(fp_in, " %c", &status->map[i][j]);
for(k = 0; k < 2; k++) {
status->pannels[i][j][k].y = i;
status->pannels[i][j][k].x = j;
status->pannels[i][j][k].leg = k;
status->pannels[i][j][k].temp_answer = UNKNOWN;
status->pannels[i][j][k].correct_answer = UNKNOWN;
if(status->map[i][j] == 'S') {
status->pannels[i][j][k].correct_answer = 0;
push(status, &status->pannels[i][j][k]);
if(k == 1) {
status->map[i][j] = 0;
}
}
}
if(status->map[i][j] == 'T') {
status->map[i][j] = 0;
}
else if(status->map[i][j] >= '0' && status->map[i][j] <= '9') {
status->map[i][j] -= '0';
}
}
}
status->min_temp = NULL;
}
void getAnswer(Status *status)
{
int i, j, answer = UNKNOWN;
Pannel *pannel;
while(1) {
pannel = (Pannel*)pop(status);
while(pannel != NULL) {
setTempAnswer(status, pannel);
pannel = (Pannel*)pop(status);
}
setMinPannel(status);
if(status->min_temp == NULL) break;
push(status, status->min_temp);
}
for(i = 0; i < status->width; i++) {
if(status->map[0][i] == 0) {
for(j = 0; j < 2; j++) {
if (answer > status->pannels[0][i][j].correct_answer) {
answer = status->pannels[0][i][j].correct_answer;
}
}
}
}
if(answer == UNKNOWN) answer = -1;
fprintf(fp_out, "%d\n", answer);
}
void setMinPannel(Status *status)
{
int i, j, k;
int temp = UNKNOWN;
/* マップの全検索で仮の最短距離が最も小さいパネルを探す */
for(i = 0; i < status->height; i++) {
for(j = 0; j < status->width; j++) {
for(k = 0; k < 2; k++) {
if(temp > status->pannels[i][j][k].temp_answer) {
status->min_temp = &status->pannels[i][j][k];
temp = status->pannels[i][j][k].temp_answer;
}
}
}
}
if(temp == UNKNOWN) {
status->min_temp = NULL;
}
else {
status->min_temp->correct_answer = status->min_temp->temp_answer;
status->min_temp->temp_answer = UNKNOWN;
}
}
void setTempAnswer(Status *status, Pannel *pannel)
{
int i, j;
int another = (pannel->leg + 1) % 2;
/* 移動条件に基づいて、x_index, y_index に数値を代入する。移動の可不可は後で判定 */
for(i = 1; i < 4; i++) {
for(j = i - 3; j < 4 - i; j++) {
int y_index, x_index;
y_index = pannel->y + j;
if(pannel->leg == RIGHT) {
x_index = pannel->x - i;
}
else {
x_index = pannel->x + i;
}
/* x_index, y_index がマップの範囲内で、かつそのマスが移動可能なら、
仮の最短距離の更新処理をする。 */
if(x_index >= 0 && x_index < status->width) {
if(y_index >= 0 && y_index < status->height) {
int map_status = status->map[y_index][x_index];
if(map_status >= 0 && map_status <= 9) {
int temp = pannel->correct_answer + map_status;
if(status->pannels[y_index][x_index][another].correct_answer == UNKNOWN) {
if (status->pannels[y_index][x_index][another].temp_answer > temp) {
status->pannels[y_index][x_index][another].temp_answer = temp;
}
}
}
}
}
}
}
}
&br;
&br;
&br;
英語のスペルミスってかなり恥ずかしい…。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
