指定された回数で移動できる経路は何通り？

指定された回数で移動できる経路は何通り？

締め切りが 2017/07/18 10:00 AM なので，その 1 分後に投稿されるように予約

設問

横に m マス、縦に n マス並んだ格子状のマスがあり、
左上の隅から右下の隅までマスの周囲または対角線に沿って移動することを考えます。
ただし、対角線は左上から右下への線のみ可能とします。
（縦でも横でも斜めでも、いずれも1回で1マス分移動します）
移動は「右」「下」「右下」のいずれかとし、左や上、左上などに移動することはできません。

標準入力から m, n と合わせて移動回数 a がスペース区切りで与えられるとき、ちょうど a 回の移動で
右下の隅に到達する経路の数が何通りあるかを求め、標準出力に出力してください。
ただし、m, n は20以下の正の整数、a は m + n 以下の正の整数とします。

例えば、m = 3, n = 2, a = 3のとき、以下のような3通りが考えられます。

【入出力サンプル】
標準入力
3 2 3

標準出力
3

======================================================================

各ノードにおいて，次のノードへの移動法は 3 通り。
可能性のある径路は 3^a 通りあるが，そのうちには，枠外へはみ出したり，出口以外の枠内にとどまるものもある。
素直に数え上げるプログラムは以下の通りであるが，当然ながら，これでは a が大きくなると計算時間が掛かりすぎる。m=10, n=12, a=20 でも，無理である。

tricombinations = function(p) {
    retval = matrix(" ", nrow = 3^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep("R", (3^p/3^n)), rep("D", (3^p/3^n)),
            rep("F", (3^p/3^n))), length = 3^p)
    }
    retval
}

f = function(m, n, a) {
    m = m+1
    n = n+1
    G = function(w) {
        x = y = 1
        for (i in seq_along(w)) {
            if (w[i] != "D") {
                x = x+1
            }
            if (w[i] != "R") {
                y = y+1
            }
            if (board[x, y] == 2) {
                return(i == a)
            } else if (board[x, y] == 0) {
                return(FALSE)
            }
        }
        return(FALSE)
    }
    n1 = n+1
    m1 = m+1
    board = matrix(0, n1, m1)
    board[1:n, 1:m] = 1
    board[n, m] = 2
    w = tricombinations(a)
    sum(apply(w, 1, G))
}
f(3, 2, 3) # 3
f(4, 5, 6) # 60
#f(10, 12, 20)
#f(20, 20, 25)
f(15, 15, 10) # 0

別の方法を試みる。再帰プログラムであるが，メモ化する必要がある。
g(m, n, a) の解は，g(m-1, n, a-1) + g(m, n-1, a-1) + g(m-1, n-1, a-1) により求められる。

f = function(m, n, a) {
    m = m+1 # 横方向のノード数
    n = n+1 # 縦方向のノード数
    memo = array(-1, dim = c(m, n, a))
    g = function(m, n, a) {
        if (m < 1 || n < 1) {
            return(0)
        }

        if (memo[m, n, a] != -1) {
            return(memo[m, n, a])
        }

        if (a < max(m, n)-1 || a > m + n - 2) {
            0 ->> memo[m, n, a]
            return(0)
        } else if ((m == 1 && n == 2 && a == 1) || (m == 2 && n == 1 && a == 1)) {
            1 ->> memo[m, n, a]
            return(1)
        } else if (m == 2 && n == 2 && a == 1) {
            1 ->> memo[m, n, a]
            return(1)
        } else if (m == 2 && n == 2 && a == 2) {
            2 ->> memo[m, n, a]
            return(2)
        } else {
            g(m - 1, n, a - 1) + g(m, n - 1, a - 1) + g(m - 1, n - 1, a - 1) ->> memo[m, n, a]
        }
        memo[m, n, a]
    }
    cat(g(m, n, a), "\n")
}

#s = scan(file("stdin", "r"), quiet=TRUE)
#f(s[1], s[2], s[3])

system.time({ # 0.062 sec.
f(3, 2, 3) # 3
f(4, 5, 6) # 60
f(10, 12, 20) # 8314020
f(20, 20, 25) # 823727520
f(15, 15, 10) # 0
})