【每日一题】求路径总数

超、凢脫俗 2022-12-26 13:27 97阅读 0赞

**题目来源**  
牛客网  
链接：[求路径总数][Link 1]

**题目描述**  
请计算n\*m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

输入描述：

> 每组样例输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述：

> 每组样例输出一行结果

输入：

> 2 2  
> 1 2

输出：

> 6  
> 3

**解题思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]  
如果n或者m为1，则只有一行或者一列，从左上角走到右下角的路径数为n + m。比如： 1 \* 1格子，可以先向下走，再向右走，到达右下角；或者先向右走，再向下走，到达右下角，共两条，即 1 + 1 = 2。

![在这里插入图片描述][20201205202355300.png]  
如果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 pathNum(int n, int m)
    {
        
    	if(n > 1 && m > 1)
    		return pathNum(n - 1,m) + pathNum(n,m - 1);
    	else if(((n >= 1)&&(m == 1))||((n == 1)&&(m >> 1)))
    		return n + m;
    	else
    		return 0;
    }
    int main()
    {
        
    	int n, m;
    	while(cin >> n >> m)
    	{
        
    		cout << pathNum(n, m) << endl;
    	}
    	return 0;
    }

[Link 1]: https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b?tpId=37&&tqId=21314&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: /images/20221120/615dc969a8974cd290ba84538b827b49.png
[20201205202355300.png]: /images/20221120/d9eba141b553427aba62907d8c5cda98.png