m283. 螞蟻的擴散

         這是一題標準的DP題目，假設以dp[x][y]做為起點開始走，那麼從dp[x][y]走一步後，dp[x-1][y]跟dp[x][y-1],dp[x-1][y-1]這三個位置個會增加dp[x][y]/3的機率被走到，以此類推直到X或是Y軸為0，最後計算起點跟終點的比值即可。

        下列附上程式：

import math

def cal(x, y):
    # 初始化dp陣列
    dp = [[0] * 11 for _ in range(11)]
    
    # 設定起點的機率為1
    dp[x][y] = 1*3**(x+y)
    
    # 遞迴計算dp
    for i in range(x, 0, -1):
        for j in range(y, 0, -1):
            dp[i-1][j] += dp[i][j] / 3
            dp[i][j-1] += dp[i][j] / 3
            dp[i-1][j-1] += dp[i][j] / 3
    
    ans = int(dp[x][y] - dp[0][0])
    cc = math.gcd(int(ans), int(dp[x][y]))
    dp[x][y] //= cc
    ans //= cc
    print(str(ans) + "/" + str(dp[x][y]))
    # 將分數化簡
    '''common_factor = math.gcd(int(result), 81)
    result /= common_factor'''

try:
    while True:
        x,y = [int(i) for i in input().split()]
        cal(x,y)
except:
    pass