格子走法 | LiuxiaoKun

题目描述

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

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

输出描述:
返回结果

示例1
输入

2
2

输出

解决方案

-------------
| 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;
}