> #include<stdio.h>
> #include<string.h>
> #define MAX 301
> int xs,ys,xe,ye,l;
> int mark[MAX][MAX];
> typedef  struct
> {
>          int col,row;
>          int key;
> }heapelem;
> heapelem  node[MAX*MAX];
> int  size;
> 
> void  change(int a,int b)
> {
>       int temp;
>       temp=mark[node[a].row][node[a].col];
>       mark[node[a].row][node[a].col]=mark[node[b].row][node[b].col];
>       mark[node[b].row][node[b].col]=temp;
>       
>       
>       heapelem  t;
>       t=node[a];
>       node[a]=node[b];
>       node[b]=t;
> }      
> 
> void  heapup(int id)
> {
>       int i=id;
>       while(i>1)
>      {
>                if(node[i].key>=node[i>>1].key)  break;
>                else
>                {
>                    change(i,i>>1);
>                    i=i>>1;
>                }
>      }
> }
> 
> void heapdown(int id)
> {
>      int i=id;
>      int temp;
>      while(2*i<=size)
>      {
>          if(2*i==size)  temp=2*i;
>          else temp=node[2*i].key<node[2*i+1].key?2*i:(2*i+1);
>          change(temp,i);
>          i=temp;  
>      }
> }
> void heapinsert(heapelem data)
> {
>      size++;
>      node[size]=data;
>      heapup(size);
> }
> 
> int   heappop()
> {
>     change(1,size);
>     size--;
>     heapdown(1);
>     return size+1;  
> }
> 
> void  heapdelete(int id)
> {
>       change(id,size);
>       size--;
>       heapdown(id);
> }
> 
> void heapmodify(heapelem data,int id)
> {
>      if(node[id].key<=data.key)  {
>                                   node[id]=data;
>                                   heapdown(id);}
>      if(node[id].key>data.key)  {
>                                   node[id]=data;
>                                   heapup(id);}
> }
> void init()
> {
>      scanf("%d",&l);
>      scanf("%d %d",&xs,&ys);
>      scanf("%d %d",&xe,&ye);
> }
> 
> void solve()
> {
>      int visit[MAX][MAX];
>      int dist[MAX][MAX];
>      memset(visit,0,sizeof(visit));
>      for(int i=0;i<l;i++)
>       for(int j=0;j<l;j++)
>        dist[i][j]=100000;
>      dist[xs][ys]=0;
>      size=0;
>      int m=xs,n=ys;
>      heapelem temp;
>      for(int i=1;i<l*l;i++)
>      {
>              visit[m][n]=1;
>              if(m+2<l&&n+1<l&&!visit[m+2][n+1]&&dist[m+2][n+1]>dist[m][n]+1)
>              {
>                   dist[m+2][n+1]=dist[m][n]+1;
>                   temp.key=dist[m+2][n+1];
>                   temp.row=m+2;
>                   temp.col=n+1;
>                   heapinsert(temp);
>              }
>              if(m+1<l&&n+2<l&&!visit[m+1][n+2]&&dist[m+1][n+2]>dist[m][n]+1)
>              {
>                   dist[m+1][n+2]=dist[m][n]+1;
>                   temp.key=dist[m+1][n+2];
>                   temp.row=m+1;
>                   temp.col=n+2;
>                   heapinsert(temp);
>              }
>              if(m-2>=0&&n+1<l&&!visit[m-2][n+1]&&dist[m-2][n+1]>dist[m][n]+1)
>              {
>                   dist[m-2][n+1]=dist[m][n]+1;
>                   temp.key=dist[m-2][n+1];
>                   temp.row=m-2;
>                   temp.col=n+1;
>                   heapinsert(temp);
>              }
>              if(m+2<l&&n-1>=0&&!visit[m+2][n-1]&&dist[m+2][n-1]>dist[m][n]+1)
>              {
>                   dist[m+2][n-1]=dist[m][n]+1;
>                   temp.key=dist[m+2][n-1];
>                   temp.row=m+2;
>                   temp.col=n-1;
>                   heapinsert(temp);
>              }
>              if(m-2>=0&&n-1>=0&&!visit[m-2][n-1]&&dist[m-2][n-1]>dist[m][n]+1)
>              {
>                   dist[m-2][n-1]=dist[m][n]+1;
>                   temp.key=dist[m-2][n-1];
>                   temp.row=m-2;
>                   temp.col=n-1;
>                   heapinsert(temp);
>              }
>              if(m-1>=0&&n+2<l&&!visit[m-1][n+2]&&dist[m-1][n+2]>dist[m][n]+1)
>              {
>                   dist[m-1][n+2]=dist[m][n]+1;
>                   temp.key=dist[m-1][n+2];
>                   temp.row=m-1;
>                   temp.col=n+2;
>                   heapinsert(temp);
>              }
>              if(m+1<l&&n-2>=0&&!visit[m+1][n-2]&&dist[m+1][n-2]>dist[m][n]+1)
>              {
>                   dist[m+1][n-2]=dist[m][n]+1;
>                   temp.key=dist[m+1][n-2];
>                   temp.row=m+1;
>                   temp.col=n-2;
>                   heapinsert(temp);
>              }
>              if(m-1>=0&&n-2>=0&&!visit[m-1][n-2]&&dist[m-1][n-2]>dist[m][n]+1)
>              {
>                   dist[m-1][n-2]=dist[m][n]+1;
>                   temp.key=dist[m-1][n-2];
>                   temp.row=m-1;
>                   temp.col=n-2;
>                   heapinsert(temp);
>              }
>              while(1)
>              {
>                 int a=heappop();
>                 m=node[a].row;
>                 n=node[a].col;
>                 if(!visit[m][n]) break;
>              }
>              if(m==xe&&n==ye)  
>              {
>                                 printf("%d\n",dist[m][n]);
>                                return ;
>              }
>      }
>      printf("%d\n",dist[xe][ye]);
> }
> 
> int main()
> {
>     int t;
>     scanf("%d",&t);
>     while(t--)
>     {
>              init();
>              solve(); 
>     }
> }
>                                   
>                                     
> 
> 
> 

• Re:原来dijkstra加堆优化也可以过的（附代码） (19) anchong 2009-08-18 18:04:15