0547:Commute routes

メモ化再帰で解いた。
dp[i][j][p]:=現在(i,j)にいて、状態pである。

i…南北
j…東西

p=
1…直前に曲っていて、東に進んでいる
　　→東に進み、p=3

2…直前に曲っていて、北に進んでいる
　　→北に進み、p=4

3…直前に曲っていない、東に進んでいる
　　→東に進み、p=3 　または　 北に進み、p=2

4…直前に曲っていない、北に進んでいる。
　　→北に進み、p=4　 または　 東に進み、p=1

#include<iostream>
#include<cstdio>

using namespace std;

int dp[101][101][5],w,h;

int func(int i, int j, int p){
  if(i>w || j>h)return 0;
  if(i==w && j==h)return 1;
  if(dp[i][j][p]>0)return dp[i][j][p];

  int res=0;
  if(p==1)res=func(i,j+1,3);
  else if(p==2)res=func(i+1,j,4);
  else if(p==3)res=func(i+1,j,2)+func(i,j+1,3); 
  else if(p==4)res=func(i+1,j,4)+func(i,j+1,1);
  else if(p==0)res=func(i,j+1,3)+func(i+1,j,4);

  return dp[i][j][p]=res%100000;
}

int main(void){

  while(cin >> w >> h,w|h){
    for(int i=0;i<=w;i++)
      for(int j=0;j<=h;j++)
	for(int p=0;p<5;p++)
	dp[i][j][p]=0;

    cout << func(1,1,0) << endl;
  }

  return 0;
}