poj1915 Knight Moves

题目：

在n*n的格板上,求马从一个格子移动到特定位置的最小步数。

---

思路：

双向BFS (轻松搞掉,一遍AC)

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=300;
 struct ss
{
	int x,y,t;
};
int n,T,f[N+5][N+5],ans[N+5][N+5];
ss st,en,q1[N*N+5],q2[N*N+5];
int d[8][2]={{1,2},{2,1},{-1,2},{2,-1},{-2,1},{1,-2},{-1,-2},{-2,-1}};

 void bfs()
{
	ss res,tmp;
	int l=0,r=1,ll=0,rr=1;
	q1[1]=st; q2[1]=en;
	while (l<r)
	{
		l++; res=q1[l];
		if (res.x==en.x&&res.y==en.y)
		{
			printf("%d
",res.t); return;
		}
		for (int i=0; i<8; i++)
		{
			tmp.x=res.x+d[i][0]; tmp.y=res.y+d[i][1]; tmp.t=res.t+1;
			if (tmp.x>=0&&tmp.x<n&&tmp.y>=0&&tmp.y<n)
				if (!f[tmp.x][tmp.y])
				{
					f[tmp.x][tmp.y]=1;
					ans[tmp.x][tmp.y]=tmp.t;
					r++; q1[r]=tmp;
				}
				else if (f[tmp.x][tmp.y]==2)
				{
					printf("%d
",ans[tmp.x][tmp.y]+tmp.t);
					return;
				}
		}
		ll++; res=q2[ll];
		for (int i=0; i<8; i++)
		{
			tmp.x=res.x+d[i][0]; tmp.y=res.y+d[i][1]; tmp.t=res.t+1;
			if (tmp.x>=0&&tmp.x<n&&tmp.y>=0&&tmp.y<n)
				if (!f[tmp.x][tmp.y])
				{
					f[tmp.x][tmp.y]=2;
					ans[tmp.x][tmp.y]=tmp.t;
					rr++; q2[rr]=tmp;
				}
				else if (f[tmp.x][tmp.y]==1)
				{
					printf("%d
",ans[tmp.x][tmp.y]+tmp.t);
					return;
				}
		}
	}
}

 int main()
{
	scanf("%d",&T);
	while (T--)
	{
		memset(f,0,sizeof(f));
		memset(ans,0,sizeof(ans));
		scanf("%d",&n);
		scanf("%d%d%d%d",&st.x,&st.y,&en.x,&en.y);
		st.t=en.t=0;
		f[st.x][st.y]=1; f[en.x][en.y]=2;
		bfs();
	}
	return 0;
}