中国象棋中的跳马问题(学习搜索中)

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!
思路：一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
int p,q;
int sx,sy,ex,ey;
int n,k,vis[111][111];
int hash[111][111];
int dx[]={2,2,-1,1,-2,-2,-1,1};
int dy[]={-1,1,-2,-2,-1,1,2,2};
struct nd
{
	int x,y,t;
};
int bfs()
{
	nd bmp,bemp;
	bemp.x=sx;
	bemp.y=sy;
	bemp.t=0;
	queue<nd>que; //定义一个队列
	que.push(bemp); //将bemp进队
	while(!que.empty())//队列非空
	{
		bemp=que.front(); //得到对首元素
		que.pop(); //将对首元素出队
		if(bemp.x==ex&&bemp.y==ey)
			return bemp.t;
		int xx;
		int yy;
		for(int i=0;i<8;i++)
		{
			int pp=i/2;
			if(pp==0)
				if(bemp.x+1<=p&&vis[bemp.x+1][bemp.y]==-1)
					continue;
			if(pp==1)
				if(bemp.y-1>=1&&vis[bemp.x][bemp.y-1]==-1)
					continue;
			if(pp==2)
				if(bemp.x-1>=1&&vis[bemp.x-1][bemp.y]==-1)
					continue;
			if(pp==3)
		    	if(bemp.y+1<=q&&vis[bemp.x][bemp.y+1]==-1)
					continue;
			xx=bemp.x+dx[i];
			yy=bemp.y+dy[i];
			if(xx>=1&&xx<=p&&yy>=1&&yy<=q&&vis[xx][yy]==0&&hash[xx][yy]==0)
			{
					bmp.x=xx;
					bmp.y=yy;
					bmp.t=bemp.t+1;
					que.push(bmp);
					hash[xx][yy]=-1;
			}
		}
	}
	return -1;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
		while(n--)
		{
			scanf("%d%d",&p,&q);
			scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
            memset(vis,0,sizeof(vis));
			memset(hash,0,sizeof(hash));
            int i,ox,oy;
	       	scanf("%d",&k);
            for(i=0;i<k;i++)
			{
                scanf("%d %d",&ox,&oy);
                vis[ox][oy]=-1;
			}
			int ans=bfs();
	    	if(ans>=0)
	    		printf("%d\n",ans);
    		else
		    	printf("can not reach!\n");
		}
    }
    return 0;
}