题解 GDFZOJ 【661】 过河卒

GDFZOJ原题地址戳[这儿](http://u.gdfzoj.com/problem/661) 洛谷原题地址戳[这儿](https://www.luogu.com.cn/problem/P1002) # 一、审题 $A$点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的$C$点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图$C$点上的马可以控制$9$个点（图中的$P1,P2…P8$和$C$）。卒不能通过对方马的控制点。 棋盘用坐标表示，$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} $$ # 三、代码 ```cpp #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; } ```