洛谷 P1002 过河卒

过河卒

分析：DP 先找出状态转移方程，到达一个点只有两条路，要么从上面来，要么从左边来，由此得出
dp[i][j]=dp[i-1][j]+dp[i][j-1],为了避免负数出现，整体移动一下，0移动到1就不会有负数出现了，开一个标记数组记录对方马的控制点，到达那个点dp[i][j]设为0，值得注意的是，当整体移动过后就是从（1，1）开始，而标记数组是从（0，0）开始，所以在判断一个点是否为对方马的控制点时，要将横纵坐标都减1（一开始没想到）
这题数据范围开long long
AC代码

#include<iostream>
#include<cstdio>
#define ll long long
ll a,b,n,m,dp[22][22],vis[23][23];
using namespace std;
void book(ll x,ll y)//标记马的控制点
{
    vis[x][y]=1;vis[x-1][y-2]=1;vis[x-2][y-1]=1;vis[x-2][y+1]=1;vis[x-1][y+2]=1;vis[x+1][y-2]=1;vis[x+2][y-1]=1;vis[x+2][y+1]=1;vis[x+1][y+2]=1;
}
int main()
{
    cin>>n>>m>>a>>b;book(a,b);dp[1][0]=1;for(int i=1;i<=n+1;++i){
    for(int j=1;j<=m+1;++j){
    dp[i][j]=dp[i-1][j]+dp[i][j-1];if(vis[i-1][j-1]==1) dp[i][j]=0;}}printf("%lld",dp[n+1][m+1]);return 0;
}