#include 
#include 
#define N 32 
#define W 10 
 
typedef struct STARNODE{ 
 int x;//节点的x,y坐标 
 int y; 
 int G;//该节点的G, H值 
 int H; 
 int is_snakebody;//是否为蛇身，是为1，否则为0； 
 int in_open_table;//是否在open_table中，是为1，否则为0； 
 int in_close_table;//是否在close_table中，是为1，否则为0； 
 struct STARNODE* ParentNode;//该节点的父节点 
} starnode, *pstarnode; 
 
starnode mapnode[N/2+2][N+4]; 
 
pstarnode opentable[N*N/2]; 
pstarnode closetable[N*N/2]; 
 
int opennode_count=0; 
int closenode_count=0; 
starnode food; 
 
//根据指针所指向的节点的F值，按大顶堆进行调整 
void heapadjust(pstarnode a[], int m, int n) 
{ 
 int i; 
 pstarnode temp=a[m]; 
 for(i=2*m;i<=n;i*=2) 
 { 
  if(i+1<=n && (a[i+1]->G+a[i+1]->H)>(a[i]->G+a[i]->H) ) 
  { 
   i++; 
  } 
  if((temp->G+temp->H)>(a[i]->G+a[i]->H)) 
  { 
   break; 
  } 
  a[m]=a[i]; 
  m=i; 
 } 
 a[m]=temp; 
} 
 
void swap(pstarnode a[],int m, int n) 
{ 
 pstarnode temp; 
 temp=a[m]; 
 a[m]=a[n]; 
 a[n]=temp; 
} 
 
 
void crtheap(pstarnode a[], int n) 
{ 
 int i; 
 for(i=n/2;i>0;i--) 
 { 
  heapadjust(a, i, n); 
 } 
} 
 
void heapsort(pstarnode a[], int n) 
{ 
 int i; 
 crtheap(a,n); 
 for(i=n;i>1;i--) 
 { 
  swap(a,1,i); 
  heapadjust(a, 1,i-1); 
 } 
} 
 
//x1, y1是邻域点坐标 
//curtnode是当前点坐标 
void insert_opentable(int x1, int y1, pstarnode pcurtnode) 
{ 
 int i; 
 if(!mapnode[x1][y1].is_snakebody && !mapnode[x1][y1].in_close_table)//如果不是蛇身也不在closetable中 
 { 
  if(mapnode[x1][y1].in_open_table && mapnode[x1][y1].G>pcurtnode->G+W)//如果已经在opentable中,但是不是最优路径 
  { 
   mapnode[x1][y1].G=pcurtnode->G+W;//把G值更新 
   mapnode[x1][y1].ParentNode=pcurtnode;//把该邻点的双亲节点更新 
   //由于改变了opentable中一个点的F值，需要对opentable中的点的顺序进行调整，以满足有序 
   for(i=1;i<=opennode_count;i++) 
   { 
    if(opentable[i]->x==x1 && opentable[i]->y==y1) 
    { 
     break; 
    } 
    heapsort(opentable, i); 
   } 
  } 
  else//把该点加入opentable中 
  { 
   opentable[++opennode_count]=&mapnode[x1][y1]; 
 
   mapnode[x1][y1].G=pcurtnode->G+W; 
   mapnode[x1][y1].H=(abs(food.x-x1)+abs(food.y-y1))*W; 
   mapnode[x1][y1].in_open_table=1; 
   mapnode[x1][y1].ParentNode=pcurtnode; 
   heapsort(opentable, opennode_count); 
  } 
 } 
} 
 
//寻找当前点的四邻域点，把符合条件的点加入opentable中 
void find_neighbor(pstarnode pcurtnode) 
{ 
 int x=pcurtnode->x; 
 int y=pcurtnode->y; 
 
 if(x+1<=N/2) 
 { 
  insert_opentable(x+1, y, pcurtnode); 
 } 
 if(x-1>=1) 
 { 
  insert_opentable(x-1, y, pcurtnode); 
 } 
 if(y+1<=N+1) 
 { 
  insert_opentable(x,y+1, pcurtnode); 
 } 
 if(y-1>=2) 
 { 
  insert_opentable(x,y-1, pcurtnode); 
 } 
} 
 
int search_road(pstarnode startnode, pstarnode endnode) 
{ 
 int is_search_road=0; 
 opennode_count=0; 
 closenode_count=0; 
 pstarnode pcurtnode; 
 
 opentable[++opennode_count]=startnode;//起始点加入opentable中 
 startnode->in_open_table=1; 
 startnode->ParentNode=NULL; 
 startnode->G=0; 
 startnode->H=(abs(endnode->x-startnode->x)+abs(endnode->y-startnode->y))*W; 
 
 if(startnode->x==endnode->x && startnode->y==endnode->y)//如果起点和终点重合 
 { 
  is_search_road=1; 
  return is_search_road; 
 } 
 
 while(1) 
 { 
  //取出opentable中第1个节点加入closetable中 
  pcurtnode=opentable[1]; 
  opentable[1]=opentable[opennode_count--]; 
 
  closetable[++closenode_count]=pcurtnode; 
  pcurtnode->in_open_table=0; 
  pcurtnode->in_close_table=1; 
 
  if(pcurtnode->x==endnode->x && pcurtnode->y==endnode->y) 
  { 
   is_search_road=1; 
   break; 
  } 
 
  find_neighbor(pcurtnode); 
 
  if(!opennode_count)//如果opentable已经为空，即没有找到路径 
  { 
   break; 
  } 
 } 
 
 return is_search_road; 
} 
 
int main(void) 
{ 
 int i, j; 
 pstarnode startnode; 
 
 for(i=0;ix, temp->y); 
  temp=temp->ParentNode; 
 }while(temp); 
 
 return 0; 
}