2006Dの解答の変更点

追加された行はこの色です。
削除された行はこの色です。
2006Dの解答へ行く。
2006Dの解答の差分を削除
[[ACM/ICPC]]&br;
&br;
&br;
[[2006Dの問題:http://www.acm-japan.org/past-icpc/domestic2006/contest/all_ja.html#section_D]]
[[2006Dの問題:http://www.acm-japan.org/past-icpc/domestic2006/contest/all_ja.html#section_D]]&br;
&br;
&br;
回答者：[[ほへい]]&br;
&br;
解法：全方向へ移動の繰り返し。&br;
　　　　getAnswer, move, isMovable あたりの処理を頑張ったと自分では思ってます。&br;
&br;
所要時間：60分&br;
&br;
速度：データセット２秒弱&br;
&br;
実行環境：PenM 1.6GHz 512M Win2000&br;
&br;
 #include <stdio.h>
 
 FILE *fp_in, *fp_out;
 static char *f_source = "2006D_in.txt";
 static char *f_answer = "2006D_out.txt";
 
 typedef struct {
    int field_data[20][20];
    int height, width;
    int x, y;
 } Field;
 
 Field first_state;
 
 void setField(void);                                // データセットの読み込み
 int getAnswer(int count, Field field);              // 再帰関数
 int move(int count, int dx, int dy, Field field);   // 移動の処理
 int isMovable(int dx, int dy, Field *field);        // 移動できるか・ゴールしたかの判定
                                                     // 移動した場合Fieldの改変
 
 int main(void)
 {
    fp_in = fopen(f_source, "r");
    fp_out = fopen(f_answer, "w");
    
    while(1) {
        int answer;
        fscanf(fp_in, "%d%d", &first_state.width, &first_state.height);
        if(first_state.width == 0 && first_state.height == 0) break;
        
        setField();
        answer = getAnswer(1, first_state);
        if(answer == 11) answer = -1;
        
        fprintf(fp_out, "%d\n", answer);
    }
    fclose(fp_out);
    fclose(fp_in);
    
    return 0;
 } 
 
 void setField()
 {
    int i, j;
    for(i = 0; i < first_state.height; i++) {
        for(j = 0; j < first_state.width; j++) {
            fscanf(fp_in, "%d", &first_state.field_data[i][j]);
            if(first_state.field_data[i][j] == 2) {
                first_state.x = j;
                first_state.y = i;
            }
        }
    }
 }
 
 int getAnswer(int count, Field field)
 {
    int temp, answer;
    if(count > 10) return 11;
    answer = move(count, 0, 1, field);
    temp = move(count, 0, -1, field);
    answer = (answer > temp) ? temp : answer;
    temp = move(count, 1, 0, field);
    answer = (answer > temp) ? temp : answer;
    temp = move(count, -1, 0, field);
    answer = (answer > temp) ? temp : answer;
    return answer;
 }
 
 int move(int count, int dx, int dy, Field field)
 {
    Field temp = field;
    int moving = isMovable(dx, dy, &temp);
    if(moving == 2) {
        return count;
    }
    else if(moving == 1) {
        return getAnswer(count + 1, temp);
    }
    return 11;
 }
 
 int isMovable(int dx, int dy, Field *field)
 {
    int count = 0;
    Field temp;
    temp = *field;
    while(1) {
        temp.x += dx;
        temp.y += dy;
        
        if(temp.x >= temp.width || temp.x < 0) {
            break;
        }
        else if(temp.y >= temp.height || temp.y < 0) {
            break;
        }
        else if(temp.field_data[temp.y][temp.x] == 1) {
            if(count == 0) break;
            else {
                temp.field_data[temp.y][temp.x] = 0;
                temp.x -= dx;
                temp.y -= dy;
                *field = temp;
                return 1;
            }
        }
        else if(temp.field_data[temp.y][temp.x] == 3) {
            return 2;
        }
        count++;
    }
    return 0;
 }
2006Dの解答 の変更点

2006Dの解答の変更点
