1915.c

poj1915求移动棋子到特定位置的最少次数,BFS经典题目

#include <stdio.h>
#include <string.h>
#define MAXN 300

typedef struct node
{
	int x,y;
	int d;
}node;
int my[8]={1,2,2,1,-1,-2,-2,-1};
int mx[8]={-2,-1,1,2,2,1,-1,-2};
char hash[MAXN][MAXN];
node q[100000],s,e;
int head,tail;
int l;
int ans;

void init()
{
	scanf("%d",&l);
	scanf("%d%d",&s.x,&s.y);
	scanf("%d%d",&e.x,&e.y);
	memset(hash,0,sizeof(hash));
}

void bfs()
{
	int i;
	node v;
	int x,y;

	while (head<tail)
	{
		v=q[++head];		
		if (v.x==e.x && v.y==e.y)
		{
			ans=v.d;
			break;
		}
		for (i=0 ;i<8 ;i++)
		{
			x=v.x+mx[i];
			y=v.y+my[i];
			if (x<0 || y<0 || x>=l || y>=l ) continue;
			if (hash[x][y]>0) continue;
			hash[x][y]=1;
			q[++tail].x=x;
			q[tail].y=y;
			q[tail].d=v.d+1;
		}
	}
}

void work()
{
	head=-1;
	tail=0;
	q[0].x=s.x;
	q[0].y=s.y;
	q[0].d=0;
	hash[s.x][s.y]=1;
	bfs();
	printf("%d\n",ans);
}

main()
{
	int n;
	
	freopen("0.txt","r",stdin);
	scanf("%d",&n);
	while (n--)
	{
		init();
		work();
	}
}