1921：【02NOIP普及组】过河卒

本文主要是介绍1921：【02NOIP普及组】过河卒，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1921：【02NOIP普及组】过河卒
【题目描述】
如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。

同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为方马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2…P8和C）。卒不能通过对方的控制点。

棋盘用坐标表示，A点（0，0）、B点（n, m）(n,m为不超过20的整数，并由键盘输入)，同样马 的位置坐标是需要给出的（约定：C≠A，同时C≠B）。现在要求你计算出卒从A点能够到达B点的路径的条数。

【输入】
B点的坐标（n,m）以及对方马的坐标（X,Y） {不用判错}

【输出】
一个整数（路径的条数）。

【输入样例】
6 6 3 2
【输出样例】
17
看到这题我们第一想到暴力，那暴力代码如下

#include<bits/stdc++.h>
using namespace std;
const int fx[]={0,-2,-1,1,2,2,1,-1,-2};
const int fy[]={0,1,2,2,1,-1,-2,-2,-1};
int dx[]={1,0};
int dy[]={0,1};
int n,m,x,y;
long long ans;
int s[40][40];
void dfs(int xxx,int yyy){if(xxx==n&&yyy==m){ans++;return ;}for(int i=0;i<2;i++){//暴力枚居所有 可行 int xx=xxx+dx[i];int yy=yyy+dy[i];if(xx>=2&&xx<=n&&yy>=2&&yy<=m&&s[xx][yy]==0){s[xx][yy]=1;dfs(xx,yy);s[xx][yy]=0;}}
}
int main(){cin>>n>>m>>x>>y;n+=2;m+=2;x+=2;y+=2;//防越界 for(int i=0;i<=8;i++) s[x+fx[i]][y+fy[i]]=1;//标记不能走的地方 dfs(2,2);cout<<ans;return 0;
}

这样只能拿60分因为超时了，而且剪枝似乎也没用，因为ans已经到了long long了
那100分解法如下

#include<bits/stdc++.h>
using namespace std;
const int fx[]={0,-2,-1,1,2,2,1,-1,-2};
const int fy[]={0,1,2,2,1,-1,-2,-2,-1};
int n,m,x,y;
long long f[40][40];
bool s[40][40];
int main(){cin>>n>>m>>x>>y;n+=2;m+=2;x+=2;y+=2;//防越界 f[2][1]=1;s[x][y]=1;for(int i=1;i<=8;i++) s[x+fx[i]][y+fy[i]]=1;//标记不能走的地方 for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){if(s[i][j]) continue; f[i][j]=f[i-1][j]+f[i][j-1];//状态转移方程 }}cout<<f[n][m];//结果 return 0;
}

原理很简单状态转移方程啊呸呸。

这是小时候大家或多或少见过的题目，就是一点到另一点有多少条路线。而这种题目也很简单，标数法（c++话讲就是递推）你求出到每个点有多少条路线，公式是到上面点的路线数加右边点的路线数就是答案，这也是这类状态转移方程的由来。注意的是起点的x轴与y轴上面的点全为1 ，随后递推出终点

这篇关于1921：【02NOIP普及组】过河卒的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---