题解 GDFZOJ 【661】 过河卒

· · 个人记录

GDFZOJ原题地址戳这儿

洛谷原题地址戳这儿

一、审题

棋盘用坐标表示，$A$ 点$(0,0)$、$B$点$(n,m)$（$n,m$为不超过$20$的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从$A$点能够到达$B$点的路径的条数。 很明显，这道题用暴搜是不行的，所以要用$Dp

二、做题

我们首先定义状态，我们设f_{i,j}为从点(0,0)走到点(i,j)一共有多少种方案，然后就可以开始愉快地推式子啦

首先我们知道f_{i,j}可以从f_{i-1,j}和f_{i,j-1}转移过来，因为如果要走到点(i,j)，就一定要么要经过(i-1,j)，要么要经过(i,j-1)，而且只能从这两个点走过来。所以我们可以很容易就推出一个式子:

f_{i,j}=f_{i-1,j}+f_{i,j-1}

可是我们还有“马”没有处理呢！其实这个也很简单，因为没法走到被马控制的点，所以只需要针对马控制的点(i,j)，将f_{i,j}改为0就行了

所以我们就顺利地推出来了

f_{i,j}=\begin{cases}f_{i,j-1}+f_{i-1,j}&(\text{点}(i,j)\text{不为被马控制的点})\\0&(\text{点}(i,j)\text{为被马控制的点})\end{cases}

三、代码

#include <bits/stdc++.h>
using namespace std;
long long int a,b,n,m,aa[22][22],zou[23][23];
void bj(long long int x,long long int y)
{
    zou[x][y]=1;
    zou[x-1][y-2]=1;
    zou[x-2][y-1]=1;
    zou[x-2][y+1]=1;
    zou[x-1][y+2]=1;
    zou[x+1][y-2]=1;
    zou[x+2][y-1]=1;
    zou[x+2][y+1]=1;
    zou[x+1][y+2]=1;
}
int main()
{
    cin>>n>>m>>a>>b;
    bj(a,b);
    aa[1][0]=1;
    for(int i=1;i<=n+1;++i)
    {
        for(int j=1;j<=m+1;++j)
        {
            aa[i][j]=aa[i-1][j]+aa[i][j-1];
            if(zou[i-1][j-1]) aa[i][j]=0;
        }
    }
    printf("%lld",aa[n+1][m+1]);
    return 0;
}