1915.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 300
typedef struct
{
	int y,x;
}data;
data st,ed;
int n;
data que[NMAX*NMAX];
int xp[8]={1,2,2,1,-1,-2,-2,-1},yp[8]={-2,-1,1,2,2,1,-1,-2};
int m[NMAX][NMAX];
void solve()
{
	int p,q;
	p=q=0;
	que[0]=st;
	q++;
	int i,j;
	for(i=0;i<NMAX;i++)
		for(j=0;j<NMAX;j++)
			m[i][j]=INF;
	data cp,tp;
	m[st.y][st.x]=0;
	while(p<q)
	{
		cp=que[p++];

		for(i=0;i<8;i++)
		{
			tp.y=cp.y+yp[i];
			tp.x=cp.x+xp[i];
			if(tp.y<0||tp.x<0||tp.y>=n||tp.x>=n)
				continue;
			if(m[tp.y][tp.x]>m[cp.y][cp.x]+1)
			{
				m[tp.y][tp.x]=m[cp.y][cp.x]+1;
				que[q++]=tp;
			}

		}
	}
	

}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int t;
	
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		scanf("%d%d",&st.y,&st.x);
		scanf("%d%d",&ed.y,&ed.x);
		solve();
		printf("%d\n",m[ed.y][ed.x]);
	}

		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}