题解 | [NOIP2002 普及组] 过河卒

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 棋盘行数
# @param m int整型 棋盘列数
# @param x int整型 马的横坐标
# @param y int整型 马的纵坐标
# @return int整型
#
class Solution:
    def crossRiver(self , n: int, m: int, x: int, y: int) -> int:
        # write code here
        m,n=m+1,n+1
        dp=[[0]*(m) for _ in range(n)]
        dict1={(x,y),(x-1,y-2),(x-1,y+2),(x-2,y-1),(x-2,y+1),(x+2,y-1),(x+2,y+1),(x+1,y-2),(x+1,y+2)}
        for i in range(0,n):
            for j in range(0,m):
                if (i,j) not in dict1:
                    if i==0 and j==0:
                        dp[i][j]=1
                    elif i==0:
                        dp[i][j]=dp[i][j-1]
                    elif j==0:
                        dp[i][j]=dp[i-1][j]
                    else:
                        dp[i][j]=dp[i-1][j]+dp[i][j-1]
                else:
                    dp[i][j]=0
        return dp[-1][-1]