洛谷 P1002 DP解法

#include<bits/stdc++.h>

#define ll long long

ll a,b,n,m,l[22][22],ma[23][23];//map需要开大点QwQ

using namespace std;

void bj(ll x,ll y)//标记马的控制点
{
    ma[x][y]=1;
    ma[x-1][y-2]=1;
    ma[x-2][y-1]=1;
    ma[x-2][y+1]=1;
    ma[x-1][y+2]=1;
    ma[x+1][y-2]=1;
    ma[x+2][y-1]=1;
    ma[x+2][y+1]=1;
    ma[x+1][y+2]=1;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
    bj(a,b);
    l[1][0]=1;//为了把应该有一步的一步给过去
    for(int i=1;i<=n+1;++i)
    {
        for(int j=1;j<=m+1;++j)
        {
            l[i][j]=l[i-1][j]+l[i][j-1];//一个点的路径来自左方与上方
            if(ma[i-1][j-1]) l[i][j]=0;//如果被马控制那么是0
        }
    }
    printf("%lld",l[n+1][m+1]);//整体向右下挪一下
    return 0;
}