AOJ 0547 Commute routes

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

解法
動的計画法。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MOD = 100000;

typedef pair<int, int> P;
typedef pair<P, P> PP;

PP dp[101][101];

int main(){
	int h, w;
	for(int i=0; i < 101; i++){
		dp[i][0] = PP(P(0,0), P(0,0));
		dp[0][i] = PP(P(0,0), P(0,0));
	}
	while(scanf("%d %d", &h, &w) && h + w != 0){
		dp[2][1] = PP(P(0,0), P(1,0));
		dp[1][2] = PP(P(1,0), P(0,0));
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				if((!(i==2&&j==2))&&(i==1||i==2)&&(j==1||j==2)) continue;
				PP ta = dp[i][j-1];
				PP yo = dp[i-1][j];
				dp[i][j] = PP(
					P((ta.first.first + ta.first.second) % MOD,
					  ta.second.first ),
					P((yo.second.first + yo.second.second) % MOD,
					  yo.first.first )
				);
			}
		}
		PP pp = dp[h][w];
		printf("%d\n", (pp.first.first + pp.first.second + pp.second.first + pp.second.second) % MOD);
	}
	return 0;
}