PKU 2704-Pascal's Travels

問題概要

NxNの非負整数が入ったマスがある．
(x,y)から移動出来る場所は(x,y)での値をdとすると，(x+d,y)か(x,y+d)とする．
(0,0)から(N-1,N-1)に移動する経路数を求めよ．

解法

(0,0)に近い所から順に動的計画法で計算する．

実装(C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long int lli;
struct State{
	int x,y,d;
	State(int x,int y):x(x),y(y){
		d=x+y;
	}
};
const bool operator<(const State &a,const State &b){
	return a.d>b.d;
}
int n;
int dx[2]={1,0},dy[2]={0,1};
inline bool valid(int x,int y){return x>=0&&x<n&&y>=0&&y<n;}
vector<string> MAP;
lli ac[35][35];
lli solve(){
	memset(ac,0,sizeof(ac));
	ac[0][0]=1;
	priority_queue<State> que;
	que.push(State(0,0));
	while(!que.empty()){
		State now(que.top());que.pop();
		int dist=MAP[now.x][now.y]-'0';
		if(dist==0)continue;
		for(int i=0;i<2;i++){
			int nx=now.x+dx[i]*dist,ny=now.y+dy[i]*dist;
			if(valid(nx,ny)){
				if(ac[nx][ny]==0){
					que.push(State(nx,ny));
				}
				ac[nx][ny]+=ac[now.x][now.y];
			}
		}
	}
	return ac[n-1][n-1];
}
int main() {
	for(;cin>>n;){
		if(n==-1)break;
		MAP=vector<string>(n);
		for(int i=0;i<n;i++){
			cin>>MAP[i];
		}
		cout<<solve()<<endl;
	}
	return 0;
}