鬼ごっこをシミュレートするプログラム練習問題が解けずに困っております (ID:72434)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2108&lang=jp
リンク先問題を解くコードなのですが上手くとけず困っております。

2人の移動を地道にシミュレートして、再帰探索で解こうとしています。
木構造の探索で、ブルースは探索の先から帰ってきたルートのうち、一番短時間で捕まえられるルートを選べばいい。
アーロンは一番長く逃げ切れる探索経路を選べばいい。
という考え方で再帰で解こうとしています。

ブルースとアーロンの位置が過去にあった配置になったらそこはループになるのでmoveOKsA moveOKsBに記憶しておき、捕まえるまでのターン数として巨大な数myMaxを返しておく。

この考え方で記述したのですが、何か考え違いかポカミスがあるらしく上手くとくことができません。
できるだけ自力で解きたいので、どなたかアドバイスをお願いします。

#include <stdio.h>
void solve();
int searchA(int a,int b,int deep,bool stop);
int searchB(int a,int b,int deep,bool stop);

int map[51][51];//
int m;
int myMax=1000000000;
bool moveOKsA[51][51];
bool moveOKsB[51][51];

int main()
{
	
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&m);
		solve();
	}
}

void solve(){
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&map[i][j]);
			moveOKsA[i][j]=true;
			moveOKsB[i][j]=true;
		}
	}
	int a,b;
	scanf("%d %d",&a,&b);
	int ans=searchA(a,b,1,false);
	printf("ans=%d\n",ans);
}

int searchA(int a,int b,int deep,bool stop)
{
	//アーロンの移動
	int maxCatch=0;
	int t;
	if(a==b){
		 moveOKsA[a][b]=false;
		 return deep;
	}
	if(moveOKsA[a][b]==false && stop==false) return myMax;
	moveOKsA[a][b]=false;
	for(int i=0;i<m;i++)
	{
		if(map[a][i]==1)
		{
			t=searchB(i,b,deep,false);
			
			if(t>maxCatch)
			{
				maxCatch=t;
			}
			
		}
	}
	if(stop==false)
	{
		t=searchB(a,b,deep,true);
		if(t>maxCatch) maxCatch=t;
	}
	return maxCatch;
}

int searchB(int a,int b,int deep,bool stop){
	//キャッチできたらターンを返す
	int minCatch=myMax;
	int t;
	
	if(a==b){
		moveOKsB[a][b]=false;
		return deep;
	}
	if(moveOKsB[a][b]==false && stop==false) return myMax;
	moveOKsB[a][b]=false;
	for(int i=0;i<m;i++){
		if(map[b][i]==1){
			t=searchA(a,i,deep+1,false);
			if(t<minCatch) minCatch=t;
		}
	}
	if(stop==false){
		t=searchA(a,b,deep+1,true);
		if(t<minCatch) minCatch=t;
	}
	
	return minCatch;
}

←解決時は質問者本人がここをチェックしてください。

戻る