AOJ 0230 Ninja Climbing

こんにちは川です。

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

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

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;

    }

}