822-走方格-递归搜索树-·-二维

824. 走方格 (递归搜索树 · 二维)

原题链接

描述： 给定一个 n×m 的方格阵，沿着方格的边线走，从左上角 (0,0) 开始，每次只能往右或者往下走一个单位距离，问走到右下角 (n,m) 一共有多少种不同的走法。

输入格式 共一行，包含两个整数 n 和 m。

输出格式 共一行，包含一个整数，表示走法数量。

数据范围

1≤n,m≤10

输入样例：

2 3

输出样例：

10

分析

• 每次到达新的位置时进行判断
  • 若到达终点 (n, m) 则计数加一

代码

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 0; // 定义边界 n 和 m

void ff(int k, int l) { // 递归遍历
    if (k == n && l == m) { // 如果同时抵达边界，则满足条件
        ans++;
    } else if (k <= n && l <= m) { // 判断未越界，进行选择
        ff(k + 1, l); // 向下移动一格
        ff(k, l + 1); // 向右移动一格
    }
}

int main() {
    cin >> n >> m;
    ff(0, 0); // 从(0,0)位置开始遍历到(n,m)
    cout << ans;
    return 0;
}