105學年度彰雲嘉區複賽程式設計題Q1(方格棋盤的走法)

一、方格棋盤的走法

假設輸入一個方格棋盤的寬X與高Y，方格之座標左上角標示為(0,0)，右下角標示為(X-1, Y-1)。每次只能往右走一格或者往下走一格，如範例圖形。假設要從左上角(0,0)走到右下角(X-1, Y-1)，請問有幾種走法？寫出一個程式從鍵盤輸入兩個整數X，Y (以一個空格分開)，其中0<X<=20, 0<Y<=20，輸出走法的個數。

輸入說明 ：

輸入第一行為一個整數 n，表示接下來會有n組測試資料。

接下來有 n 行，每行有兩個整數，數字間以一個空格區隔，分別代表方格棋盤的寬及高。

輸出說明 ：

輸出走法的個數，每個測試資料輸出一行。

範例1輸入：
2

4 8

8 8

範例1輸出：

120

3432

範例2輸入：
1

6 7

範例2輸出：

462

Python code：

"""

利用遞迴寫組合數C(n,m)，並解方格棋盤走法問題

"""

def C(n,m):

    if n<m:

        return 0

    elif m==0 or n==m:

        return 1

    else:

        return C(n-1,m)+C(n-1,m-1)

k=int(input())

c=[]

d=[]

for i in range(k):

    a,b=(int(x) for x in input().split())

    c.append(a)

    d.append(b)

for i in range(k):

    print(C(c[i]+d[i]-2,c[i]-1))

😊 這題不是常見的走線上捷徑的問題，而是走格子內，所以在輸入的長跟寬，都需減1，再取組合數，才是正解。