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;
}
}