2006Dの解答

ACM/ICPC


2006Dの問題


回答者：ほへい

解法：全方向へ移動の繰り返し。
　　　　getAnswer, move, isMovable あたりの処理を頑張ったと自分では思ってます。

所要時間：60分

速度：データセット２秒弱

実行環境：PenM 1.6GHz 512M Win2000

#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;
}