贤鱼的刷题日常---P1002 [NOIP2002 普及组] 过河卒---详细题解

🏆今日学习目标： 🍀理解，学会过河卒题目 ✅创作者：贤鱼 🎉个人主页：贤鱼的个人主页 🔥专栏系列：c++

题目

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A 点 (0, 0)、B 点 (n, m)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入格式 一行四个正整数，分别表示B 点坐标和马的坐标。 输出格式 一个整数，表示所有的路径条数。 输入输出样例 输入 #1复制 6 6 3 3 输出 #1复制 6 说明/提示 对于 100% 的数据1≤n,m≤20，0≤ 马的坐标 ≤20。

思路

对于这道题，我们首先可以算出来马的八个移动点的范围，将他们设为1，这样子就处理好了马。，然后就是一个简单的dp题了，题目中说了，人只能向下或者向右，所以vis[i][j]=vis[i-1][j]+vis[i][j-1],下面来看看代码

AC代码

#include
#include
#include
#include
using namespace std;
long mapp[1001][1001];
long vis[1001][1001];
long x,y,xx,yy;//记得开longlong
long n,m;
long ans=0;
int main(){
	cin>>x>>y>>xx>>yy;
	n=x,m=y;
	mapp[xx][yy]=1;
	if(xx > 1 && yy != 0)   mapp[xx - 2][yy - 1] = 1;
	if(xx  1 && yy != 20)  mapp[xx - 2][yy + 1] = 1;
	if(xx  1)   mapp[xx - 1][yy - 2] = 1;
	if(xx != 0 && yy  1)  mapp[xx + 1][yy - 2] = 1;
	if(xx != 20 && yy