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;
}
返答が付かないので解決済みとします。
編集 削除おやおや、どもども。
こないだ、オレの簡単問題を解いたな。
本人か誰か知らんが。
どうだ？少しだけレベルの高い（普通問題）クラスにチャレンジしてみるかね？
それとも、どこかでカンニングしてるのかね？カネカネ。
このコードは動くの？
試してないが。
逃げたの？
まず、迷路がどんなんかわからんのに返答のしようもないね。
複雑な迷路ルーチンを見せたまえ。
見込みがありそうなら、ココの村人になれるかもよ。
http://www.shoeisha.co.jp/
就職可。
ちなみにオレはアンタのやりたいプログラムは簡単に書けるぜ。
はい、すいません。
前はカンニングを全くしてないみたいに言いましたがあの後自分のカンニングを調べ直しました。
ほとんどの問題を自力で解いたのですが、どうしてもわからない問題を人に聞いたり思いっきり調べて解いたり答えをみてといたりしました。
カンニングのリストはこちらです。
http://www14.atwiki.jp/c21coterie/pages/427.html
現在325問中１６問もカンニングして解いています。
カンニングはしていますが、問題を解くのが目的でなく基礎的なアルゴリズムを学ぶのが目的なのですから多少カンニングが入るのはしかたないと考えています。
迷路がどんなものかはリンク先を見れば誰にでもわかりますよ。
>ちなみにオレはアンタのやりたいプログラムは簡単に書けるぜ。
翔泳ミキオさんは凄いですね。
リンク先問題はゲーム理論を応用したり行列の収束を利用したりかなりむずかしい方法で解くらしいです。
私は他の回答者の答えを見ても難しすぎて全く理解できませんでした。
理解できないのでまだこの問題はアセプトしていません。
はい、ミキオ三の言うとおりまだまだ私は低レベルな初心者です。
リンク先については見てみることにしますね。