読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

AOJ 0230 Ninja Climbing

AOJ volume2

こんにちは川です。

今回は、メモ化再帰っぽいことしてますね。

再帰をする際に一度来たことがあれば、ループしているということなので

NAを出しています。

それ以外は、今いる場所と場合によって一つ上を調べて

それに合った行動をしているだけです。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
 
bool wall[2][103]={};
int wallnum[2][101];
 
int serch(int n,int now,int num,int co)
{
    if(wall[now][num])return -1;
    wall[now][num]=1;
    if(num>=n-1)return co;
    if(wallnum[now][num]==0||wallnum[now][num]==1&&wallnum[now][num+1]!=1){
        now++;
        if(now>1)now=0;
        for(int i=2;i>0;i--)
       if(wallnum[now][num+i]!=2)return serch(n,now,num+i,co+1);
        return serch(n,now,num,co+1);
    }
    else if(wallnum[now][num]==1)return serch(n,now,num+1,co);
    else return serch(n,now,num-1,co);
}
int main()
{
    int n;
    while(cin>>n,n){
 
        for(int i=0;i<2;i++){
            for(int j=0;j<n;j++)cin>>wallnum[i][j];
        }
        int ans[2];
        for(int i=0;i<2;i++){
            memset(wall,0,sizeof(wall));
            ans[i]=serch(n,i,0,0);
        }
        if(ans[0]==-1&&ans[1]==-1)cout<<"NA\n";
        else if(ans[0]==-1||ans[1]==-1)cout<<max(ans[0],ans[1])<<endl;
        else cout<<min(ans[0],ans[1])<<endl;
    }
}