#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加堆优化也可以过的（附代码） (5530) anchong 2009-08-18 18:03:11
  • Re:原来dijkstra加堆优化也可以过的（附代码） (19) anchong 2009-08-18 18:04:15
• Re:原来dijkstra加堆优化也可以过的（附代码） (5530) wimson 2010-03-19 23:24:39
• Re:原来dijkstra加堆优化也可以过的（附代码） (5530) wimson 2010-03-19 23:24:40