40分,救救孩子!!!
查看原帖
40分,救救孩子!!!
1328046
sugarbear楼主2024/3/30 17:54
input_line=input()
split_data=input_line.split()
target_x=int(split_data[0])
target_y=int(split_data[1])
horse_x=int(split_data[2])
horse_y=int(split_data[3])
#可使用n, m, x, y = map(int, input().split())来替代

#马控制点
dp = [[0] * (target_y+1) for _ in range(target_x+1)]
dp[horse_x][horse_y]=-1
dp[horse_x+1][horse_y+2]=-1
dp[horse_x+2][horse_y+1]=-1
dp[horse_x-1][horse_y+2]=-1
dp[horse_x-2][horse_y+1]=-1
dp[horse_x-2][horse_y-1]=-1
dp[horse_x-1][horse_y-2]=-1
dp[horse_x+1][horse_y-2]=-1
dp[horse_x+2][horse_y-1]=-1

#使用动态规划求解
dp[0][0]=1
for i in range(target_x+1):
    for j in range(target_y+1):
        #跳过马控制点
        if dp[i][j]==-1:
            continue
        if i>0 and dp[i-1][j]!=-1:
            dp[i][j]+=dp[i-1][j]
        if j>0 and dp[i][j-1]!=-1:
            dp[i][j]+=dp[i][j-1]

print(dp[target_x][target_y])

想知道是漏考虑啥了啊

2024/3/30 17:54
加载中...