AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
KAIK_art

AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

#1

投稿記事 by KAIK_art » 12年前

サンプルを自機で試し、うまくいったので投稿したところランタイムエラーになってしまいます。自分ではどこがおかしいのか分かりません。
どこが間違っているのでしょうか?
問題ページ
↓コード

コード:

#include <iostream>
using namespace std;
void SET(int c,int d,int x,int y,int few[105][105]){
			if(d==1){
				few[y][x]  =few[y+1][x]  =few[y+2][x]  =few[y+3][x]  =c;
				few[y][x+1]=few[y+1][x+1]=few[y+2][x+1]=few[y+3][x+1]=c;
			}else if(d==0){
				few[y][x]  =few[y][x+1]  =few[y][x+2]  =few[y][x+3]  =c;
				few[y+1][x]=few[y+1][x+1]=few[y+1][x+2]=few[y+1][x+3]=c;
			}
}
bool e=false;
bool SAT(int c,int y,int x,int yg,int xg,int few[105][105]){
	if(e)return true;
	if(y==yg&&x==xg){  e=true; return true;}
	if(few[y][x+1]==c)	SAT(c,y,x+1,yg,xg,few);
	if(few[y+1][x]==c)	SAT(c,y+1,x,yg,xg,few);
	if(few[y][x-1]==c)	SAT(c,y,x-1,yg,xg,few);
	if(few[y-1][x]==c)	SAT(c,y+1,x,yg,xg,few);
	if(e)return true;
	return false;
}
int main(){
	int w, h, xs, ys, xg, yg, n;
	int c, d, x, y;
	while(cin>>w>>h){
		if(w==0&&h==0) return NULL;
		int few[105][105]={0,};
		cin>>xs>>ys>>xg>>yg>>n;
		for(int i=1;i<=n;i++){
			cin>>c>>d>>x>>y;
			SET(c,d,x,y,few);
		}
		if(few[ys][xs]!=few[yg][xg])	cout<<"NG"<<endl;
		else{
			e=false;
			if(SAT(few[ys][xs],ys,xs,yg,xg,few))	cout<<"OK"<<endl;
			else							    	cout<<"NG"<<endl;
		}
	}
	return NULL;
}
無駄が多く、みにくいソースですみません。

アバター
a5ua
記事: 199
登録日時: 13年前

Re: AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

#2

投稿記事 by a5ua » 12年前

19行目

コード:

if(few[y-1][x]==c)  SAT(c,y+1,x,yg,xg,few);
                           ^
                          y-1 の間違いではありませんか?

KAIK_art

Re: AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

#3

投稿記事 by KAIK_art » 12年前

a5ua さんが書きました:19行目

コード:

if(few[y-1][x]==c)  SAT(c,y+1,x,yg,xg,few);
                           ^
                          y-1 の間違いではありませんか?
指摘ありがとうございます。
訂正しました。

ですがやっぱりランタイムエラーから抜け出せません。

アバター
a5ua
記事: 199
登録日時: 13年前

Re: AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

#4

投稿記事 by a5ua » 12年前

再帰関数呼び出しが深くなりすぎて、スタックオーバーフローになっている可能性が考えられます。

コード:

(x  , y  ) -> (x+1, y  ) -> (x+2, y  ) -> …
                         -> (x+1, y+1) -> …
                         -> (x  , y  ) -> (x+1, y  )
上記のように、同じ場所を何度も探索しないように、

コード:

bool visited[105][105];
のようなフラグを用意しておき、
visited[y][x]がtrueとなったら、再帰呼び出しをしないようにしてみてはどうでしょうか?
(visited[y][x]がfalseなら、trueに更新した後、再帰呼び出しを行う)

たいちう
記事: 418
登録日時: 13年前

Re: AOJの問題0207「Block」が何回やってもランタイムエラーになってしまいます

#5

投稿記事 by たいちう » 12年前

a5uaさんが指摘している原因でしょうね。
1問目のゴールを(9,9)から(7,9)に変更すれば同じ現象が発生すると思いますので、
デバッグしやすいかと。

閉鎖

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