题目描述

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如上图 C 点上的马可以控制 9 个点（图中的P1，P2，⋯P8 和 C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A 点（0，0）、B 点$（n,m）(n,m \leq 20)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入描述

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出描述

一个整数，表示所有的路径条数。

输入输出样例

示例 1

输入

6 6 3 3

输出

6

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

思路

我们定义状态dp[][]为卒子走到坐标（i，j）时能走的条数

如果不考虑马的控制，i,j) 点的路径条数等于它上面和左边的路径条数之和，即

我们这道题中要考虑马的位置，当卒子走到马的控制点时，我们跳过这个点，让这个点还为0，不会影响控制点下边和左边的dp[][]，这样我们就可以继续计算其他点的dp[][]的值了。

代码

1. n,m,x,y=map(int,input().split()) 2. 3. dp=[[0]*40 for i in range(40)] 4. #可以控制的八个点和初始位置 5. dx=[0,2,1,-1,-2,-2,-1,1,2] 6. dy=[0,1,2,2,1,-1,-2,-2,-1] 7. 8. lst=[[0,0]] 9. 10. def check(x,y): 11. global n,m 12. if xn or ym: 13. return False 14. else: 15. return True 16. 17. #走到（0，0）位置的路只有一条 18. dp[0][0]=1 19. for i in range(9): 20. X=x+dx[i] 21. Y=y+dy[i] 22. if check(X,Y)==False: 23. continue 24. else: 25. lst.append([X,Y]) 26. 27. for i in range(0,n+1): 28. for j in range(0,m+1): 29. if [i,j] in lst: 30. continue 31. else: 32. dp[i][j]=dp[i-1][j]+dp[i][j-1] 33. print(dp[n][m])