第9回日本情報オリンピック 予選 問題5 通勤経路

DP

ショートコーディング大会みたいになった。

#include <bits/stdc++.h>

using namespace std;

const int mod = 100000;
int w,h,dp[102][102][4];

int main(){
	cin >> w >> h;
	dp[1][1][0] = 1;dp[1][1][3] = 1;
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if(i == 1 && j == 1)continue;
			dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][2];
			dp[i][j][1] = dp[i-1][j][0];
			dp[i][j][2] = dp[i][j-1][3];
			dp[i][j][3] = dp[i][j-1][1] + dp[i][j-1][3];
			for(int k = 0;k < 4;k++)dp[i][j][k]%=mod;
		}
	}
	cout << (dp[h][w][0]+dp[h][w][3])%mod << endl;
	return 0;
}