はやし屋

競技プログラミングのメモ きたない

aoj 0230: Ninja Climbing

まともな初投稿(?)
めんどくさそうだったけどそうでもなかった
幅優先

#include<iostream>
#include<queue>
using namespace std;
struct P{  
  int ch,cost,h;  
  P(int ch,int h,int cost):ch(ch),h(h),cost(cost) {}  
};
int n;
int stage[2][11111];
int calc(){
  bool used[2][11111] = {};
  queue < P > que;
  que.push(P(1,0,0));
  que.push(P(0,0,0));
 
  while(!que.empty()){
    P p = que.front();que.pop();
    if(stage[p.ch][p.h] == 1){
      while(p.h < n && stage[p.ch][p.h] == 1)p.h++;
      p.h--;
    } else if(stage[p.ch][p.h] == 2){
      while(p.h > 0 && stage[p.ch][p.h] == 2)p.h--;
    }
    if(used[p.ch][p.h])continue;
    used[p.ch][p.h] = true;
    if(p.h == n-1)return p.cost;
    for(int i = 0 ; i < 3 ; ++i){
      if(n > p.h+i)
    que.push(P((p.ch+1)&1,p.h+i,p.cost+1));
    }
  }
  return -1;
}     
 
int main(){
  while(cin >> n && n){
    for(int i = 0 ; i < 2 ; ++i)
      for(int j = 0 ; j < n ; ++j)
    cin >> stage[i][j];
    int jud = calc();
    if(~jud)cout << jud << endl;
    else cout << "NA" << endl;
  }
}