poj1915 Knight Moves 双向广度搜索

题目链接：http://poj.org/problem?id=1915

//国际象棋中马 的问题
//为了学习双向广度就拿这道开刀,
//双向广度搜索是以首尾的状态分别进行广度搜索，
//当解答树的结点重合是就得到最优解
//这里要考虑到如何让两个广度搜索同时进行,可以定义两个队列,
//当哪个队列不空时执行一次，再去判断另一个队列，两个队列都为空时退出


// AC 360ms
//代码:

#include<iostream>
#include<queue>
#include<cstdio>
#define MAX 302

using namespace std;

int x[]={1,2,2,1,-1,-2,-2,-1};
int y[]={2,1,-1,-2,-2,-1,1,2};
struct point
{
	int x,y;
};
int len;

int aa[MAX][MAX],bb[MAX][MAX];//aa[i][j],bb[i][j]分别表示正向和反向到(i,j)的步数

bool isok(int x,int y)
{
	if(x<0||x>=len||y<0||y>=len)return false;
	return true;
}

int BBFS(int x1,int y1,int x2,int y2)
{
	if(x1==x2&&y1==y2)
	{return 0;}
	point p0,p1;
	p0.x=x1;
	p0.y=y1;
	p1.x=x2;
	p1.y=y2;
	queue<point >q[2];
	q[0].push(p0);
	q[1].push(p1);
	int i,j;
	
	for(i=0;i<len;i++)
		for(j=0;j<len;j++)
			aa[i][j]=bb[i][j]=-1;
		aa[x1][y1]=0;
		bb[x2][y2]=0;
		while(!(q[0].empty()&&q[1].empty()))
		{
			if(!q[0].empty())//正向
			{
				point temp=q[0].front();
				q[0].pop();
				for(i=0;i<8;i++)
				{
					int tx=temp.x+x[i];
					int ty=temp.y+y[i];
					if(isok(tx,ty))
					{
						if(aa[tx][ty]==-1)
						{
							aa[tx][ty]=aa[temp.x][temp.y]+1;
							point temp_2={tx,ty};
							q[0].push(temp_2);
						}
						if(bb[tx][ty]!=-1)
							return aa[tx][ty]+bb[tx][ty];
					}
				}
			}
			if(!q[1].empty())//反向
			{
				point temp=q[1].front();
				q[1].pop();
				for(i=0;i<8;i++)
				{
					int tx=temp.x+x[i];
					int ty=temp.y+y[i];
					if(isok(tx,ty))
					{
						if(bb[tx][ty]==-1)
						{
							bb[tx][ty]=bb[temp.x][temp.y]+1;
							point temp_2={tx,ty};
							q[1].push(temp_2);
						}
						if(aa[tx][ty]!=-1)
							return aa[tx][ty]+bb[tx][ty];
					}
				}
			}
		}
}

int main()
{
	int cas;
	scanf("%d",&cas);
	int x1,y1,x2,y2;
	while(cas--)
	{
		scanf("%d",&len);
		scanf("%d%d",&x1,&y1);
		scanf("%d%d",&x2,&y2);
		printf("%d\n",BBFS(x1,y1,x2,y2));
	}
	return 0;
}