AOJ : 0230 - Ninja Climbing (忍者のビル登り)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
日本語の問題文なので説明省略です.

アルゴリズム

状態として, [左右のビルどちらにいるか, ビルの何階にいるか, 何回ジャンプしたか] を持たせて, 左右のビルの１階から幅優先させて解きました.

プログラム

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

class P{
public:
  int b,h,cost; //ビルのどっちにいるか,ビルの階数,ジャンプ回数

  P(int _b,int _h,int _cost){
    b = _b;
    h = _h;
    cost = _cost;
  }
};

int n;
int b[2][101];
bool closed[2][101];

int solve(void){
  queue<P> q;
  memset(closed,0,sizeof(closed));
  q.push(P(0,0,0));
  q.push(P(1,0,0));

  while(!q.empty()){
    P p = q.front(); q.pop();
    if(b[p.b][p.h] == 1){ //はしご
      while(p.h<n && b[p.b][p.h]==1) p.h++;
      p.h--;
    }
    else if(b[p.b][p.h] == 2){ //すべる壁
      while(b[p.b][p.h]==2) p.h--;
    }

    if(closed[p.b][p.h]) continue;
    closed[p.b][p.h] = true;

    if(p.h == n-1) return p.cost;

    rep(i,3) if(n > p.h + i) {
      q.push(P(!p.b,p.h+i,p.cost+1));
    }
  }

  return -1;
}

int main(void){
  while(cin>>n,n){
    rep(i,2) rep(j,n) cin>>b[i][j];

    int cal = solve();
    if(cal == -1) cout<<"NA\n";
    else cout<<cal<<endl;
  }

  return 0;
}