4644018_wa.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
struct st
{
	int x,y;
}e[100];
int f,b;
int step[10][10];
int chang,x,y,gx,gy;
st get(st x,int count)
{
	switch(count)
	{
	case 1:x.x+=2;x.y+=1;return x;
	case 2:x.x+=2;x.y-=1;return x;
	case 3:x.x-=2;x.y+=1;return x;
	case 4:x.x-=2;x.y-=1;return x;
	case 5:x.x+=1;x.y+=2;return x;
	case 6:x.x+=1;x.y-=2;return x;
	case 7:x.x-=1;x.y+=2;return x;
	case 8:x.x-=1;x.y-=2;return x;
	}
	return x;
}
int BFS(int x,int y)
{
	memset(step,100,sizeof(step));
	step[0][0]=0;
	e[0].x=0;e[0].y=0;
	f=0;b=1;
	while(f<b)
	{
		if(e[f].x==x&&e[f].y==y)return step[x][y];
		else
		{
			for(int count=1;count<=8;count++)
			{
				st temp=get(e[f],count);
				if(temp.x<0)temp.x*=-1;
				if(temp.y<0)temp.y*=-1;
				//cout<<temp.x<<" "<<temp.y<<" ";
				if(step[temp.x][temp.y]>step[e[f].x][e[f].y]+1)
				{
					step[temp.x][temp.y]=step[e[f].x][e[f].y]+1;
					e[b++]=temp;
				}
			}
		}
		f++;
	}
	return -1000;
}
void slove(int x,int y)
{
	if(x<0) x*=-1;
	if(y<0) y*=-1;
	int result=0;
	while(x>7||y>7)
	{
		result++;
		if(y>x) 
		{	
			y-=2;
			x--;
		}
		else
		{
			x-=2;
			y--;
		}
		if(x<0) x*=-1;
		if(y<0) y*=-1;
	}
	cout<<result+BFS(x,y)<<endl;
}
int main()
{
	int testnumber;
	cin>>testnumber;
	for(int count=1;count<=testnumber;count++)
	{
		cin>>chang;
		cin>>x>>y>>gx>>gy;
		slove(gx-x,gy-y);
	}
	return 0;
}