题目描述

请编写一个函数(允许增加子函数),计算n x m的棋盘格子(n为横向的格子数,m为竖向的格子数)沿着各自边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。

输入描述:
输入两个正整数

输出描述:
返回结果

示例1
输入

2
2

输出

6

解决方案

-------------
| 1 | 2 | 3 |
-------------
| 4 | 5 | 6 |
-------------
| 7 | 8 | 9 |
-------------
1. 对于上面的n*m(3*3)的格子,有两种情况
a. 如果n或者m为1,则只有一行或者一列,从左上角走到右下角的路径数为n + m
比如: 1 * 1格子,可以先向下走,再向右走,到达右下角;或者先向右走,
再向下走,到达右下角,共两条,即 1 + 1 = 2,对于1 * m和 n * m的
情况同学们自己画一下
b. 如果n,m都大于1,那么走到[n][m]格子的右下角只有两条路径,
<1>: 从[n - 1][m]格子的右下角向下走,到达
<2>: 从[n][m - 1]格子的右下角向右走,到达
所以走到[n][m]格子的右下角的数量为[n-1][m] + [n][m - 1],可以通过递归 实现,情况a
为递归的终止条件。
#include<iostream>
using namespace std;

int sum(int x,int y)
{
    if(x>1&&y>1)
    {
        return sum(x,y-1)+sum(x-1,y);
    }else if((x>=1 && y==1)|| (x==1)&&(y>=1)){
        return x+y;
    }else{
        return 0;
    }
}
int main()
{
    int col,row;
    while(cin>>col>>row){
        cout<<sum(row,col)<<endl;
    }
    return 0;
}