POJ3009の問題について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
asdjack
記事: 22
登録日時: 8年前

POJ3009の問題について

#1

投稿記事 by asdjack » 6年前

POJの問題を解いていたのですが、
http://poj.org/problem?id=3009

コード:

 
#include<stdio.h>
int map[21][21],m[5]={0,1,0,-1,0},mh,mw,mt;

void s(int h,int w,int t)
{
	int i,j,x=w,y=h;
	if(t<11)
	{
		for(i=j=0;i<4;x=w,y=h,j=0,i++)
		{
			while(++j)
			{
				y+=m[i];
				x+=m[i+1];
				if(map[y][x]==3)
				{
					mt=t+1<mt?t+1:mt;
					return;
				}
				if((0>y||y>=mh||0>x||x>=mw)||(j==1&&map[y][x]==1))
					break;
				if(map[y][x]==1)
				{
					map[y][x]--;
					s(y-m[i],x-m[i+1],t+1);
					map[y][x]++;
					break;
				}
			}
		}
	}
}

int main()
{
	int i,j,sh,sw;
	for(;;)
	{
		scanf("%d%d",&mw,&mh);
		if(mw==0&&mh==0)
			return 0;
		for(i=0;i<mh;i++)
			for(j=0;j<mw;j++)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j]==2)
					sh=i,sw=j;
			}
		mt=11;
		s(sh,sw,0);
		printf("%d\n",mt>10?-1:mt);
	}
}

サンプルインプットや20×20などの検証はあっているのにもかかわらず
WrongAnswerになってしまいました。
おかしな点がありましたらご指摘お願いいたします。

box
記事: 1745
登録日時: 9年前

Re: POJ3009の問題について

#2

投稿記事 by box » 6年前

main関数の戻り値がint型であるにもかかわらず
正しくreturnしていない、という話だったりして…。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

asdjack
記事: 22
登録日時: 8年前

Re: POJ3009の問題について

#3

投稿記事 by asdjack » 6年前

>>boxさん
ご指摘ありがとうございます。
入力が0,0だったときbreakして最後にreturn0するようにしましたが
やはりWrong Answerでした。
何か見落としているケースがあるのでしょうか…

non
記事: 1097
登録日時: 9年前

Re: POJ3009の問題について

#4

投稿記事 by non » 6年前

次の場合はどうなるのが正しいですか。

最初の入力
6 1
1 1 2 1 1 3
出力は-1ですね。続けて、
5 1
3 1 0 2 0
このときの答えは?
non

asdjack
記事: 22
登録日時: 8年前

Re: POJ3009の問題について

#5

投稿記事 by asdjack » 6年前

>>nonさん
2となるのが正しいはずです。
自分のプログラムだと1になっていました。

コード:

#include<stdio.h>
int map[21][21],m[5]={0,1,0,-1,0},mh,mw,mt;

void s(int h,int w,int t)
{
	int i,j,x=w,y=h;
	if(t<11)
	{
		for(i=j=0;i<4;x=w,y=h,j=0,i++)
		{
			while(++j)
			{
				y+=m[i];
				x+=m[i+1];
				if((0>y||y>=mh||0>x||x>=mw)||(j==1&&map[y][x]==1))
					break;
				if(map[y][x]==3)
				{
					mt=t+1<mt?t+1:mt;
					return;
				}
				if(map[y][x]==1)
				{
					map[y][x]--;
					s(y-m[i],x-m[i+1],t+1);
					map[y][x]++;
					break;
				}
			}
		}
	}
}

int main()
{
	int i,j,sh,sw;
	for(;;)
	{
		scanf("%d%d",&mw,&mh);
		if(mw==0&&mh==0)
			break;
		for(i=0;i<mh;i++)
			for(j=0;j<mw;j++)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j]==2)
					sh=i,sw=j;
			}
		mt=11;
		s(sh,sw,0);
		printf("%d\n",mt>10?-1:mt);
	}
	return 0;
}
修正して提出したところ、Acceptされました。
範囲外かチェックする前にゴールかを判定していたのがいけなかったようです。
ご指摘ありがとうございました。

閉鎖

“C言語何でも質問掲示板” へ戻る