中国象棋中的跳马问题（BFS）

题目描述
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
输入
第一行输入n表示有n组测试数据。

每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。

输出
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
样例输入
2
9 10
1 1 2 3
0
9 10
1 1 2 3
8
1 2
2 2
3 3
3 4
1 4
3 2
2 4
1 3
样例输出
1
can not reach!
提示
此题是一个搜索题，可用DFS或BFS，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

本题有多种地方需要考虑。首先，重复点和障碍点需要设立2个数组判别，一个数组会导致程序错误！（亲身经历！！！）；
其次，马跳的8个方向与4个阻碍马腿跳的点需要方向一致，否则会出现输出超限与内存超限问题！！！；
最后，BFS的判断条件一定要考虑清楚，本人考虑的是1：拐点是否有障碍；2：跳的那个点是否在棋盘内，跳的点不能是重复点，跳的点不能是障碍点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct dir
{
	int x;
	int y;
};
dir D[8] = { {-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2} };  //马跳的8个方向
int zhang[4][2] = { -1,0,0,1,1,0,0,-1 };  //8个方向对应的4个拐马角点。
int X,Y;  //棋盘大小
int a[6];
queue<int> Q;
int visit[101][101];  //判断是否为重复点
int can[101][101];  //判断是否为障碍点
int cnt;
int check(int a, int b)  //检查点是否在棋盘内
{
	if (a > 0 && a <= X && b > 0 && b <= Y)
		return 1;
	else
		return 0;
}
void BFS()
{
	int H, L;
	cnt = 0;
	Q.push(a[0]);
	Q.push(a[1]);
	Q.push(cnt);
	visit[a[0]][a[1]] = 1;
	while (!Q.empty())
	{
		H = Q.front(); Q.pop();
		L = Q.front(); Q.pop();
		cnt = Q.front(); Q.pop();
		if (H == a[2] && L == a[3])
		{
			cout << cnt << endl;
			return;
		}
		for (int i = 0; i < 8; i++)
		{
			if (can[H + zhang[i / 2][0]][L + zhang[i / 2][1]] == 0)  //判断该点是否为拐马角点
				if (check(H + D[i].x, L + D[i].y) && !visit[H + D[i].x][L + D[i].y]&&!can[H + D[i].x][L + D[i].y])  
				/*判断跳的那个点是否在棋盘内，跳的点不能是重复点，跳的点不能是障碍点*/
				{
					Q.push(H + D[i].x);
					Q.push(L + D[i].y);
					Q.push(cnt + 1);
					visit[H + D[i].x][L + D[i].y] = 1;
				}
		}
	}
	cout<<"can not reach!"<<endl;
}
int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		cin >> X >> Y;
		while (!Q.empty())
			Q.pop();
		memset(visit, 0, sizeof(visit));
		memset(can, 0, sizeof(can));
		cin >> a[0] >> a[1] >> a[2] >> a[3];
		int m;
		cin >> m;
		while (m--)
		{
			int a, b;
			cin >> a >> b;
			can[a][b] = 1;
		}
		BFS();
	}
	return 0;
}

本题的陷阱比较多，需要细心注意！