07年度-ACM-ICPC国内予選 2007D †
予選時:未回答
まだ未確定の部分を距離の短い方から順に確定していく。ダイクストラ法もどき。 途中で壁にぶつかってコードを一から書き直したので、とんでもなく時間を使ってしまった。最後にどうしても値が合わなかったのだが、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 <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; } } } } } 解説 #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; } } } } } } } }
|