AOJ 0547:Commute routes

考え抜けたので良かったです.
状態がからむDPは初めてかも...!

解けた記念に再帰解とDP解を両方載せておきます.
＜再帰解＞
横を向いている→１、縦を向いている→２として、愚直にシュミレーションです.(マップからはみ出す場合があるので、そこに注意すればOK）
５つのテストケース中、３つくらい解けます.

#include <stdio.h>

int dfs(int y, int x, int dir)
{
    if (((x == 1 || x == 0) && y == 1) || (x == 1 && (y == 1 || y == 0))){
        return (1);
    }
    else if (x <= 0 || y <= 0){
        return (0);
    }
    
    if (dir == 1){
        return ((dfs(y, x - 1, 1) + dfs(y - 2, x, 2)) % 100000);
    }
    else {
        return ((dfs(y - 1, x, 2) + dfs(y, x - 2, 1)) % 100000);
    }
}


int main(void)
{
    int i, j;
    
    while (1){
        scanf("%d%d", &i, &j);
        
        if (i + j == 0){
            break;
        }
        
        printf("%d\n", (dfs(j, i - 1, 1) + dfs(j - 1, i, 2))% 100000);
    }
    
    return (0);
}

＜DP解＞
再帰解とほぼ一緒です.
このときはマップ外に行くことは無いので、簡単にかけてしまいます！

#include <stdio.h>

int main(void)
{
    int i, j;
    int dp[101][101][2] = {0};
    
    for (i = 1; i <= 100; i++){
        dp[i][1][0] = dp[1][i][0] = dp[i][1][1] = dp[1][i][1] = 1;
    }
    
    for (i = 2; i <= 100; i++){
        for (j = 2; j <= 100; j++){
            dp[i][j][0] = (dp[i][j - 1][0] + dp[i - 2][j][1]) % 100000;
            dp[i][j][1] = (dp[i - 1][j][1] + dp[i][j - 2][0]) % 100000;
        }
    }
    
    
    while (1){
        scanf("%d%d", &i, &j);
        
        if (i + j == 0){
            break;
        }
        
        printf("%d\n", (dp[j][i - 1][0] + dp[j - 1][i][1]) % 100000);
    }
    
    return (0);
}