题目描述
如图，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 x<0 or x>n or y<0 or y>m: 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])
