2006Dの解答
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[ACM/ICPC]]&br;
&br;
&br;
[[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;
速度:データセット2秒弱&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;
}
終了行:
[[ACM/ICPC]]&br;
&br;
&br;
[[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;
速度:データセット2秒弱&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;
}
ページ名: