题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0,0)、B点(n,m)(n, m为不超过202020的整数)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入输出格式
输入格式：
一行四个数据，分别表示B点坐标和马的坐标。
输出格式：
一个数据，表示所有的路径条数。
输入输出样例
说明
结果可能很大！
分析：dp就可以，，
A 0 0 0 0 0 0
0 0 X 0 X 0 0
0 X 0 0 0 X 0
0 0 0 M 0 0 0
0 X 0 0 0 X 0
0 0 X 0 X 0 0
0 0 0 0 0 0 B
--------------》
1 1 1 1 1 1 1
1 2 X 1 X 1 2
1 X 0 1 1 X 2
1 1 1 M 1 1 3
1 X 1 1 0 X 3
1 1 X 1 X 0 3
1 2 2 3 3 3 6
这样动态方程就可以很容易求出来了，dp[i][j]=dp[i-1][j]+dp[i][j-1]...
另外，为了防止数组越界，便于处理，我爸每个点的位置横纵坐标都加了一，这也导致了下面代码中动态方程那里多了一个max的原因，为了处理第一个数。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn =; ll dp[maxn][maxn];
bool check[maxn][maxn];/*判断这个点有没有被马盯着*/
int n,m,mx,my;/*b点位置以及马的位置*/
const int fx[]={-,-,,,,,-,-};
const int fy[]={,,,,-,-,-,-}; int main(int argc, char const *argv[])
{
scanf("%d%d%d%d",&n,&m,&mx,&my);
n+=;m+=;mx+=;my+=;
dp[][]=;
check[mx][my]=;/*把马的位置标记为不可走*/
for( int i=; i<; i++ ){/*把马能到的位置也标记为不可走*/
check[mx+fx[i]][my+fy[i]]=;
}
for(int i=; i<=n; i++ ){
for( int j=; j<=m; j++ ){
if(check[i][j]) continue;
dp[i][j]=max(dp[i][j],dp[i-][j]+dp[i][j-]);
}
}
cout<<dp[n][m]<<endl;
return ;
}