> #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也过了的 (134) happynp 2007-05-23 15:49:35
• Re:不知道怎么wa的 1915也过了的 (15) happynp 2007-05-23 15:50:51