过河卒（洛谷）

题目

原题

题目描述

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$
点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0,0)$、$B$ 点 $(n,m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例 #1

样例输入 #1

6 6 3 3

样例输出 #1

6

提示

对于 $100\%$ 的数据，$1\le n,m\le 20$，$0\le$ 马的坐标 $\le 20$。

【题目来源】

NOIP 2002 普及组第四题

思路

由于题目中限定了棋子只能向下和右走，因此这大大简化了题目难度。因此dp思路基本就明确了。如果棋子想要到达点(i,j),这里只有两点可以到达，分别是（i-1,j)和（i,j-1)。因此到达(i,j)路径数等于到达(i-1,j)和(i,j-1)的路径数之和（当然还要考虑边界情况和马的控制点），以此循环就是dp思路了。
不过使用dfs的思路更简单，因此我这里使用的是记忆搜索dfs。这里的数据量比较大因此必须使用记忆dfs，否则无法通过。dfs思路和dp差不多，一个点只能向下或向右行走，以此递归最终可以达到答案。

代码

#include<bits/stdc++.h>
using namespace std;
bool flag[21][21]={
   0};					//禁止到达的点 
long long int ans[21][21]={
   0};			//记录计算过的点的路径数量 			
pair<int,int> b;						//b点位置

long long int dfs(int x,int y){
   
	if(ans[x][y]!=0)					//该点计算过就直接返回值
		return ans[x][y];
	if(x==b.first&&y==b.second)			//到达b点
		return 1;
	if(y+1<=20&&!flag[x][y+1]&&y+1<=b.second)	//如果向下行走不会越界且不会达到马控制点就向下行走
		ans[x][y]+=dfs(x,y+1);
	if(x+1<=20&&!flag[x+1][y]&&x+1<=b.first)	//如果向右行走不会越界且不会达到马控制点就向下行走
		ans[x][y]+=dfs(x+1,y);
	return ans[x][y];
}
int main(){
   
	int dx[]={
   -1,-1,-2,-2,1,1,2,2};
	int dy[]={
   -2,2,-1,1,2,-2,-1,1};
	cin>>b.first>>b.second;
	int x,y;
	cin>>x>>y;
	flag[x][y]=true;
	for(int i=0;i<8;i++){
   		//标记马的控制点
		if(dx[i]+x>=0&&dx[i]+x<=20&&dy[i]+y>=0&&dy[i]+y<=20)
			flag[dx[i]+x][dy[i]+y]=true;   //禁止到达的点 
	}
	cout<<dfs(0,0);				//dfs
}