AOJ0230:Ninja Climbing

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230

方針

nが割と小さいのでDFSで間に合う。
これまでの最小値を保持しておいてそれが更新される場合
そこから再帰的に最小値を更新していく。

グラフを作って最短経路問題にも落とせる気がする。

以下ソースコード

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>

#define INF 1 << 28

using namespace std;

int building[2][101];
int dp[2][101];
int n;

void solve(int b, int level){
	int nb = 1 - b;
	for(int i=0;i<3;i++){
		int nl = level+i;
		if(nl >= n) continue;
		while(building[nb][nl] == 1 && building[nb][nl+1] == 1){
			nl++;
		}
		while(building[nb][nl] == 2) nl--;
		if(dp[nb][nl] > dp[b][level] + 1){
			dp[nb][nl] = dp[b][level]+1;
			solve(nb, nl);
		}
	}
}

int main(){
	while(cin >> n && n){
		int tmp=0;
		fill((int *)dp, (int *)dp+2*101, INF);
		
		for(int i=0;i<2;i++){
			for(int j=0;j<n;j++){
				cin >> building[i][j];
			}
		}
		//番兵
		building[0][n] = 0;
		building[1][n] = 0;
		
		tmp = 0;
		while(building[0][tmp] == 1 && building[0][tmp+1] == 1){
			tmp++;
		}
		dp[0][tmp] = 0;
		solve(0,tmp);
		tmp = 0;
		while(building[1][tmp] == 1 && building[1][tmp+1] == 1){
			tmp++;
		}
		dp[1][tmp] = 0;
		solve(1,tmp);
		if(dp[0][n-1] == INF && dp[1][n-1] == INF){
			cout << "NA" << endl;
		}else{
			cout << min(dp[0][n-1], dp[1][n-1]) << endl;
		}
	}
}