【题目描述】

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

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入描述】

一行四个数据，分别表示B点坐标和马的坐标。（保证所有的数据有解）

【输出描述】

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

【样例输入】

6 6 3 3

【样例输出】

6

【题目分析】

• 马走日的改编版，需求遍历整个棋盘，但是这次改成了”卒“遍历棋盘（到达目的地）。

• 卒只能向下或者向右，绝对不能走回头路，不然就可能有无数条路径了，可以用数组表示。

• 马能走的路径至多有8个（理想情况下），可以通过数组把这8个点分别表示出来，这样给定任何一个马的坐标都可以表示其余方位。

• 如果马在边界点上，有些坐标是不需要考虑的

• 一定注意是”卒“躲过”马“的袭击，到达目标点，不是”马“怎么走才能吃掉”卒“

• 题目保证有解，所以决定不存在什么”卒的起始位置就是马能跳的点“类似情况

• DFS深搜加上判断条件即可，注意m和n的最大是15

• 本题使用框架二，用flag数组表示马能走的点。

• int Search(int k)  　{  　  if  (到目的地) 输出解;  　　　else  　　　　for (i=1;i<=算符种数;i++)  　　　　　if  (满足条件)   　　　　　　　{  　　　　　　　　保存结果;  　　　                  Search(k+1);  　　　　　　　　恢复：保存结果之前的状态{回溯一步}  　　　　　　　}  　}

【参考答案】

#include<iostream>  #include<cstdio>  #include<cstring>  using namespace std;  int x,y,hx,hy; //定义B点坐标和马的坐标  int dx[2]= {0,1}; //卒的x变化  int dy[2]= {1,0}; //卒的y变化  bool flag[16][16]; //标记数组,用来标记哪些点能走或不能走  int sum; //定义总路径条数  void changeFlag(int x,int y) { //马能走的所有路径都封死,不让卒走  	flag[x][y]=1;  	flag[x-1][y-2]=1;  	flag[x-2][y-1]=1;  	flag[x-2][y+1]=1;  	flag[x-1][y+2]=1;  	flag[x+1][y-2]=1;  	flag[x+2][y-1]=1;  	flag[x+2][y+1]=1;  	flag[x+1][y+2]=1;  	//此处有个小问题，就是如果马的坐标在左边界的时候，数组有可能出现flag[-1][0]这类越界问题。但是，题目保证有解，所以在这个地方没有额外考虑  }  //使用框架二  void dfs(int sx,int sy) {  	if(sx==x && sy==y) {  		sum++;  //到达b点就累加1  		return;  	}  	for(int i=0; i<2; i++) { //卒只有两走法（下，右）  		int fx=sx+dx[i]; //当前卒的某一方向的x坐标  		int fy=sy+dy[i]; //当前卒的某一方向的y坐标  		if(flag[fx][fy]==0 && fx<=x && fy<=y) {   		//如果当前这个点没有在马的目标点上，而且没有超过目标点x,y   			flag[fx][fy]=1; //将当前点变为1，表示此点已经走过了   			dfs(fx,fy); //继续遍历下一个点   			flag[fx][fy]=0; //回溯一步   		}  	}    }  int main() {  	cin>>x>>y>>hx>>hy;  	changeFlag(hx,hy); //把马走的路径封死  	dfs(0,0); //从0,0开始遍历,注意，是 卒 的遍历，不是马  	cout<<sum<<endl;  	return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});