#include <stdio.h>
#include <math.h>
#include <memory.h>
#define  N  9
int chess[N][N];
const int lenQuene = N*N;
int d[8][2]  = {-2,-1,
                -2, 1,
				-1,-2,
				-1, 2,
				 2,-1,
				 2, 1,
				 1,-2,
				 1, 2};
typedef struct Point
{
	int x, y;
}Point;

typedef struct Quene
{
	Point  *base;
	int    head;
	int    rear;
}Quene;
Quene  S,E; //全局队列
void Init(Quene &q)
{
    q.base = new Point[lenQuene];
	q.head = 0;
	q.rear = 0;
}

void Destroy(Quene &q)
{
	delete []q.base;
}

bool IsEmpty(Quene &q)
{
   if(q.head == q.rear)
	   return true;
   else
	   return false;
}

bool IsFull(Quene &q)
{
   if((q.rear + 1)%lenQuene == q.head)
	   return true;
   else
	   return false;
}

bool EnQuene(Quene &q, Point &p) //insert
{
    if(IsFull(q))
	  return false;
	q.base[q.rear] = p;
    q.rear = (q.rear+1)%lenQuene;
	  return true;
}

bool DeQuene(Quene &q, Point &p) //delete
{
	if(IsEmpty(q))    
	  return false;
	p = q.base[q.head];
	q.head = (q.head+1)%lenQuene;
	  return true;
}

bool inner(Point s, int l)
{
	if(s.x>=0 && s.x<l && s.y>=0 && s.y<l)
		return true;
	else
		return false;
}

int BFS(Point s, Point e, int l)
{	
	if(s.x == e.x && s.y == e.y)  //起始相同      
        return 0;

    float k = ((float)abs(s.y-e.y))/((float)abs(s.x-e.x)); //直线情况
	if( k==2.0 )
		return  abs(s.y-e.y)/2;
	if( k==0.5)
		return  abs(s.y-e.y);
	
	int i = 0 , j = 0;
	Point Shere = s, Snbr; //起点
    Point Ehere = e, Enbr; //终点
	do{
       for(i = 0; i<8; i++)
	   {
		  Snbr.x = Shere.x + d[i][0];
          Snbr.y = Shere.y + d[i][1];		 
		  if(inner(Snbr,l))
		  {
			if(chess[Snbr.x][Snbr.y]==0)
			{
			   chess[Snbr.x][Snbr.y] = chess[Shere.x][Shere.y] + 1;
			   if(Snbr.x == Ehere.x && Snbr.y == Ehere.y)
				   return chess[Snbr.x][Snbr.y] - chess[Ehere.x][Ehere.y] + 1;
			   for(j = 0; j<8 ; j++)
			   {			   
		          Enbr.x = Ehere.x + d[j][0];
                  Enbr.y = Ehere.y + d[j][1];
				  if(inner(Enbr,l))
				  {
					  if(chess[Enbr.x][Enbr.y]==0)
					  {
						  chess[Enbr.x][Enbr.y] = chess[Ehere.x][Ehere.y] - 1;
					      EnQuene(E,Enbr);
					  }
					  else if(chess[Enbr.x][Enbr.y]>0)
						  return chess[Enbr.x][Enbr.y] - chess[Ehere.x][Ehere.y] + 1;					  
				  }
			   }
              EnQuene(S,Snbr);
			}
			else if(chess[Snbr.x][Snbr.y] < 0)
				return  chess[Shere.x][Shere.y] - chess[Snbr.x][Snbr.y] + 1;					
		  }	
		  else
			continue;
	   }
	}while(DeQuene(S,Shere)||DeQuene(E,Ehere));
}
int main()
{
	char str1[3],str2[3];
	Point  s , e;
	int ans;
  while(EOF!=scanf("%s",str1))
  {	
	Init(S);
    Init(E);
	scanf("%s",str2);
    s.x = int(str1[0] - 'a') - 1;
    s.y = int(str1[1] - '0') - 1;
    e.x = int(str2[0] - 'a') - 1;
	e.y = int(str2[1] - '0') - 1;
    memset(chess,0,sizeof(int)*N*N);     
	ans = BFS(s,e,8);
    printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans); 		  
   Destroy(S);
   Destroy(E);
  } 
	return 0;
}

• Re:不知道怎么wa的 1915也过了的 (3369) happynp 2007-05-23 15:47:46
  • Re:不知道怎么wa的 1915也过了的 (134) happynp 2007-05-23 15:49:35
  • Re:不知道怎么wa的 1915也过了的 (15) happynp 2007-05-23 15:50:51