题解 | #走方格的方案数#

n*m的格子有fun(n,m)种走法
到达右下角点的走法相当于到达与其相邻的两个点的走法之和
即 fun(n, m) = fun(n - 1, m) + fun(n, m -1)
fun(1, 1) = 2;
fun(1, n) = fun(1, n - 1) + 1;
fun(m, 1) = fun(m - 1, 1) + 1;

int fun(int n, int m)
{
    if (n == 1 && m == 1)
        return 2;
    else if (n == 1 && m > 1)
        return fun(n, m - 1) + 1;
    else if (n > 1 && m == 1)
        return fun(n - 1, m) + 1;
    else
        return fun(n - 1, m) + fun(n, m - 1);
}

int main(void)
{
    int n, m;
    int val = 0;
    
    scanf("%d %d", &n, &m);
    
    val = fun(n, m);
    
    printf("%d\n", val);
    return 0;
}