洛谷 P1002 DP解法

代码语言：javascript复制

#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;
}

dp

0 人点赞