棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标
输出路径总数
6 6 3 3
6
5 4 2 3
3
2 5 3 5
1
def check(x, y, i, j): # 排除马的位置 return (abs(i - x) + abs(j - y) == 3 and i != x and j != y)&nbs***bsp;(i == x and j == y) def solution(n, m, x, y): dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)] dp[0][0] = 1 for j in range(1, m + 1): # 第一行 dp[0][j] = 0 if check(x, y, 0, j) else dp[0][j - 1] for i in range(1, n + 1): # 第一列 dp[i][0] = 0 if check(x, y, i, 0) else dp[i - 1][0] for i in range(1, n + 1): # 动态转移 for j in range(1, m + 1): dp[i][j] = 0 if check(x, y, i, j) else dp[i - 1][j] + dp[i][j - 1] return dp[n][m] n, m, x, y = map(int, input().split()) print(solution(n, m, x, y))
#判断该点是不是可行点 即是否为对方马的控制点 def panduan(i,j,x,y): if (abs(i-x)+abs(j-y)==3 and i!=x and j!=y)&nbs***bsp;(i==x and j==y): return True else: return False # if __name__ == '__main__': n, m, x, y = map(int,input().split()) dp=[[1 for j in range(m+1)] for i in range(n+1)]#细节 数组的size: n+1*m+1 for j in range(1,m+1):#初始化第一行 dp[0][j]=0 if panduan(0,j,x,y) else dp[0][j-1] for i in range(1,n+1):#初始化第一列 dp[i][0]=0 if panduan(i,0,x,y) else dp[i-1][0] for i in range(1,n+1): for j in range(1,m+1): dp[i][j]=0 if panduan(i,j,x,y) else dp[i-1][j]+dp[i][j-1]#注意限制条件的把握 print(dp[-1][-1])
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
