當(dāng)前位置:首頁 > IT技術(shù) > Windows編程 > 正文

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

題目

給定一個(n×m)的方格陣,沿著方格的邊線走,從左上角((0,0))開始,每次只能往右或者往下走一個單位距離,問走到右下角((n,m))一共有多少種不同的走法。

輸入格式
共一行,包含兩個整數(shù)(n)(m)。

輸出格式
共一行,包含一個整數(shù),表示走法數(shù)量。

數(shù)據(jù)范圍
(1≤n,m≤10)
輸入樣例:
2 3
輸出樣例:
10


題解:

dfs深搜、用最小的舉例進(jìn)行模擬、任何點(diǎn)都只要向右、或者是向下兩種情況,建系來處理該問題、然后利用dfs進(jìn)行搜索、注意邊界問題即可。


代碼:

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

本文摘自 :https://www.cnblogs.com/

開通會員,享受整站包年服務(wù)立即開通 >