【题目描述】

棋盘上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;
}