AcWing822. 走方格
2021-09-04 10:27:25

题目

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

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

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

数据范围
(1≤n,m≤10)
输入样例：
2 3
输出样例：
10

题解：

dfs深搜、用最小的举例进行模拟、任何点都只要向右、或者是向下两种情况，建系来处理该问题、然后利用dfs进行搜索、注意边界问题即可。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m;
int ans;

// 深搜寻找合适方案
void dfs(int x, int y)
{
    // 临界情况
    if (x == n && y == m) ans ++;
    else 
    {
        if (y < m) dfs(x, y + 1);
        if (x < n) dfs(x + 1, y);
    }
}

int main()
{
    cin >> n >> m;
    
    dfs(0, 0);
    
    cout << ans << endl;
    
    return 0;
}