P1002 过河卒 详细题解 搜索回溯+递归 [NOIP2002 普及组]

题目描述

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

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

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

输入格式

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

输出格式

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

6 6 3 3

样例输出

6

对于100%的数据，1 <= n, m <= 20，0 <=马的坐标 <= 20。

【题目来源】

NOIP 2002 普及组第四题

题目分析

首先 A点的坐标是(0,0)(0,0)！并且，卒只能向下或向右！

我们都清楚象棋中的马是如何跳的，跳的是“日”字形。以输入样例6×6，马在(3,3)(3,3)为例，左至右分别为x，上至下分别为y。

其中C点为马的控制点。我们不妨把马的控制点a[x][y]标记为1。

样例共有6条路径：

大家仔细观察一下，马在第一排(y=0)(y=0)的走法有三种：

1. 第一排走到底，再走到目标点；
2. 第一排走到第四个0的位置，这里大家可以看出有一种路径；
3. 第一排走到倒数第二个0的位置，拐个弯到达目标位置；

这里总共33种走法；在第一列(x=0)(x=0)的走法有两种，分别是：

1. 第一列走到倒数第二个0的位置，拐个弯到达目标位置；
2. 第一列走到第四个0的位置，大家可以看出有一种路径；
3. 第一列走到底，再走到目标点；

这里总共有3种走法；加上前面的3种，共有6种！

看到这里，大家应该明白了题意，现在我们看输入输出：

1. 输入前两个数，为棋盘的长宽；
2. 输入后两个数，为马的坐标(x,y)(x,y)；

代码实现 搜索回溯 一匹马

先判断出马的所有据点坐标
判断坐标是否越界
但考虑的细节很多，代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m,x,y;  //(n,m)=终点坐标  (x,y)=马坐标 
int sum=0; //计数 
bool a[21][21]={0}; //判断是否可走 

void dfs(int x,int y){
	for(int i=1;i<=2;i++){  //有两种情况(向上或向右走) 
		if(x<=n&&y<=m&&a[x][y]==0){
			int oldx=x,oldy=y;
			if(i==1){  //向下走 防止越界 判断下面的数是否被马占领 
				x++;
			}
			if(i==2){  //向右走 防止越界 判断右边的数是否被马占领
				y++;
			}
			if(x==n&&y==m){
				sum++;
			} 
			else{
				dfs(x,y);
			}
			x=oldx,y=oldy;  //返回原值 
		}
	}
}

int main(){
	
	cin>>n>>m>>x>>y;
	
	//判断马的据点
	a[x][y]=1;
	// P1
	if(x+2<=n&&y+1<=m){
		a[x+2][y+1]=1;
	}
	// P2
	if(x+1<=n&&y+2<=m){
		a[x+1][y+2]=1;
	}
	// P3
	if(x-1>=0&&y+2<=m){
		a[x-1][y+2]=1;
	}
	// P4
	if(x-2>=0&&y+1<=m){
		a[x-2][y+1]=1;
	}
	// P5
	if(x-2>=0&&y-1>=0){
		a[x-2][y-1]=1;
	}
	// P6
	if(x-1>=0&&y-2>=0){
		a[x-1][y-2]=1;
	}
	// P7
	if(x+1<=n&&y-2>=0){
		a[x+1][y-2]=1;
	}
	// P8
	if(x+2<=n&&y-1>=0){
		a[x+2][y-1]=1;
	}
	
	dfs(0,0); 
	
	cout<<sum;
	
	return 0;
} 

因为用的是搜索回溯而不是递归，所以会超时！
测试点如下：

两匹马 偷懒思路-两匹马

偷懒思路：
这个思路是我朋友想到的（所以没加注释，应该很好懂吧）
把数组设大一点，把棋盘放到中间
这样就不用考虑越界了！代码如下：

#include<bits/stdc++.h>
using namespace std;

int s[10001][10001]={0},n,m,x1,y3,y2,x2,sum=0;

int sch(int x,int y){
	for(int i=1;i<=2;i++){
		if(s[x][y]==0&&x<=n+100&&y<=m+100){
			int p=x,l=y;
			if(i==1){
				x++;
			}
			if(i==2){
				y++;
			}
			if(n+100==x&&m+100==y){
				sum++;
			}
			else{
				sch(x,y);
			}
			x=p;
			y=l;
		}
	}
}

int main(){
	
	cin>>n>>m>>x1>>y3>>x2>>y2;
	s[x1+100][y3+100]=1; 
    s[x1+100-2][y3+100+1]=1;
	s[x1+100-2][y3+100-1]=1; 
	s[x1+100+1][y3+100-2]=1; 
	s[x1+100+1][y3+100+2]=1;  
	s[x1+100-1][y3+100+2]=1;  
	s[x1+100-1][y3+100-2]=1;
	s[x1+100+2][y3+100-1]=1;  
	s[x1+100+2][y3+100+1]=1;  
	s[x2+100-2][y2+100+1]=1;
	s[x2+100-2][y2+100-1]=1; 
	s[x2+100+1][y2+100-2]=1; 
	s[x2+100+1][y2+100+2]=1;  
	s[x2+100-1][y2+100+2]=1;  
	s[x2+100-1][y2+100-2]=1;
	s[x2+100+2][y2+100-1]=1;  
	s[x2+100+2][y2+100+1]=1;  
	s[x2+100][y2+100]=1;
	sch(100,100);
	cout<<sum; 
	
	return 0; 
} 

要注意的是，这种思路要从(100,100)开始
则 sch(100,100);

一般思路-两匹马

浅浅改一下代码就可以了！

#include<bits/stdc++.h>
using namespace std;

int n,m,xxx,yyy,xx,yy;  //(n,m)=终点坐标  (xx,yy)=第一匹马的坐标 (xxx,yyy)=第二匹马的坐标 
int sum=0; //计数 
bool a[21][21]={0}; //判断是否可走 

void dfs(int x,int y){
	for(int i=1;i<=2;i++){  //有两种情况(向上或向右走) 
		if(x<=n&&y<=m&&a[x][y]==0){
			int oldx=x,oldy=y;
			if(i==1){  //向下走 防止越界 判断下面的数是否被马占领 
				x++;
			}
			if(i==2){  //向右走 防止越界 判断右边的数是否被马占领
				y++;
			}
			if(x==n&&y==m){
				sum++;
			} 
			else{
				dfs(x,y);
			}
			x=oldx,y=oldy;  //返回原值 
		}
	}
}

int main(){
	
	cin>>n>>m>>xxx>>yyy>>xx>>yy;
	
	//判断第一匹马的据点(xx,yy)
	a[xxx][yyy]=1;
	// P1
	if(xxx+2<=n&&yyy+1<=m){
		a[xxx+2][yyy+1]=1;
	}
	// P2
	if(xxx+1<=n&&yyy+2<=m){
		a[xxx+1][yyy+2]=1;
	}
	// P3
	if(xxx-1>=0&&yyy+2<=m){
		a[xxx-1][yyy+2]=1;
	}
	// P4
	if(xxx-2>=0&&yyy+1<=m){
		a[xxx-2][yyy+1]=1;
	}
	// P5
	if(xxx-2>=0&&yyy-1>=0){
		a[xxx-2][yyy-1]=1;
	}
	// P6
	if(xxx-1>=0&&yyy-2>=0){
		a[xxx-1][yyy-2]=1;
	}
	// P7
	if(xxx+1<=n&&yyy-2>=0){
		a[xxx+1][yyy-2]=1;
	}
	// P8
	if(xxx+2<=n&&yyy-1>=0){
		a[xxx+2][yyy-1]=1;
	}
	
	//判断第二匹马马的据点(xxx,yyy) 把(xx,yy)改成(xxx,yyy)即可 
	a[xx][yy]=1;
	// P1
	if(xx+2<=n&&yy+1<=m){
		a[xx+2][yy+1]=1;
	}
	// P2
	if(xx+1<=n&&yy+2<=m){
		a[xx+1][yy+2]=1;
	}
	// P3
	if(xx-1>=0&&yy+2<=m){
		a[xx-1][yy+2]=1;
	}
	// P4
	if(xx-2>=0&&yy+1<=m){
		a[xx-2][yy+1]=1;
	}
	// P5
	if(xx-2>=0&&yy-1>=0){
		a[xx-2][yy-1]=1;
	}
	// P6
	if(xx-1>=0&&yy-2>=0){
		a[xx-1][yy-2]=1;
	}
	// P7
	if(xx+1<=n&&yy-2>=0){
		a[xx+1][yy-2]=1;
	}
	// P8
	if(xx+2<=n&&yy-1>=0){
		a[xx+2][yy-1]=1;
	}
	
	dfs(0,0); 
	
	cout<<sum;
	
	return 0;
} 

输入两匹马的位置都为（3，3）
结果仍然是6条路径，如下图

教程到这就结束了！
看我写的这么辛苦的份上，点个赞好吗~

递归代码（双马）

用递归实现更简单
递归两匹马code：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,m1x,m1y,m2x,m2y,a[105][105],b[105][105]={0};
	cin>>n>>m>>m1x>>m1y>>m2x>>m2y;
	//马的据点 
	b[m1x][m1y]=1;
	if(m1x-2>=0&&m1y-1>=0){
		b[m1x-2][m1y-1]=1;
	}
	if(m1x-1>=0&&m1y-2>=0){
		b[m1x-1][m1y-2]=1;
	}
	if(m1x+1<=n&&m1y-2>=0){
		b[m1x+1][m1y-2]=1;
	}
	if(m1x+2<=n&&m1y-1>=0){
		b[m1x+2][m1y-1]=1;
	}
	if(m1x+2<=n&&m1y+1<=m){
		b[m1x+2][m1y+1]=1;
	}
	if(m1x+1<=n&&m1y+2<=m){
		b[m1x+1][m1y+2]=1;
	}
	if(m1x-1>=0&&m1y+2<=m){
		b[m1x-1][m1y+2]=1;
	}
	if(m1x-2>=0&&m1y+1<=m){
		b[m1x-2][m1y+1]=1;
	}
	
	b[m2x][m2y]=1;
	if(m2x-2>=0&&m2y-1>=0){
		b[m2x-2][m2y-1]=1;
	}
	if(m2x-1>=0&&m2y-2>=0){
		b[m2x-1][m2y-2]=1;
	}
	if(m2x+1<=n&&m2y-2>=0){
		b[m2x+1][m2y-2]=1;
	}
	if(m2x+2<=n&&m2y-1>=0){
		b[m2x+2][m2y-1]=1;
	}
	if(m2x+2<=n&&m2y+1<=m){
		b[m2x+2][m2y+1]=1;
	}
	if(m2x+1<=n&&m2y+2<=m){
		b[m2x+1][m2y+2]=1;
	}
	if(m2x-1>=0&&m2y+2<=m){
		b[m2x-1][m2y+2]=1;
	}
	if(m2x-2>=0&&m2y+1<=m){
		b[m2x-2][m2y+1]=1;
	}
	//递归边界 
	for(int i=0;i<=m;i++){
		a[0][i]=1;
	} 
	for(int i=0;i<=n;i++){
		a[i][0]=1;
	}
	//递归 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[i][j]==0){
				a[i][j]=a[i-1][j]+a[i][j-1];
			}
		}
	}
	cout<<a[n][m]<<endl; 
}

标签： #amp