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