Algorithm 版 (精华区)

发信人: xiong (阿拉斯加棕熊), 信区: Algorithm
标  题: 1091K-Knight Moves-ZJU
发信站: 哈工大紫丁香 (2002年10月16日22:48:31 星期三), 站内信件

#include <stdio.h>
#include <iostream.h>
//October 16th 10:42 pm
int *ShortestPath(int **length,int number,int v0)
{
 int *ret,v,w,min,i;
 bool *final;
 ret=new int[number];
 final=new bool[number];
 for(v=0;v<number;v++)
 {
  final[v]=false;ret[v]=length[v0][v];
 }
 ret[v0]=0;final[v0]=true;
 for(i=0;i<number;i++)
 {
  v=v0;
  min=10000000;
  for(w=0;w<number;w++)
   if(!final[w])
    if(ret[w]<min){v=w;min=ret[w];}
  final[v]=true;
  for(w=0;w<number;w++)
   if(!final[w]&&(min+length[v][w]<ret[w]))
   {
    ret[w]=min+length[v][w];
   }
 }
 delete []final;
 return ret;
}
int main(void)
{
 int **source;
 int *des,i,j;
   char startrow,endrow;
   int startcolumn,endcolumn;
 int n=64;
 source=new int*[n];
 for(i=0;i<n;i++)source[i]=new int[n];
   for(i=0;i<n;i++)for(j=0;j<n;j++)source[i][j]=10000000;
   for(i=0;i<8;i++)
   {
      for(j=0;j<8;j++)
      {
         if((i+2>=0)&&(i+2<8))
         {
            if((j+1>=0)&&(j+1<8))
            {
               source[i*8+j][(i+2)*8+j+1]=1;
            }
            if((j-1>=0)&&(j-1<8))
            {
               source[i*8+j][(i+2)*8+j-1]=1;
            }
         }
         if((i+1>=0)&&(i+1<8))
         {
            if((j+2>=0)&&(j+2<8))
            {
               source[i*8+j][(i+1)*8+j+2]=1;
            }
            if((j-2>=0)&&(j-2<8))
            {
               source[i*8+j][(i+1)*8+j-2]=1;
            }
         }
         if((i-1>=0)&&(i-1<8))
         {
            if((j+2>=0)&&(j+2<8))
            {
               source[i*8+j][(i-1)*8+j+2]=1;
            }
            if((j-2>=0)&&(j-2<8))
            {
               source[i*8+j][(i-1)*8+j-2]=1;
            }
         }
         if((i-2>=0)&&(i-2<8))
         {
            if((j+1>=0)&&(j+1<8))
            {
               source[i*8+j][(i-2)*8+j+1]=1;
            }
            if((j-1>=0)&&(j-1<8))
            {
               source[i*8+j][(i-2)*8+j-1]=1;
            }
         }
      }
   }
   //freopen("d:\\in.txt","r",stdin);
   //freopen("d:\\out.txt","w",stdout);
   while(cin>>startrow>>startcolumn>>endrow>>endcolumn)
   {
    des=ShortestPath(source,n,(startrow-97)*8+startcolumn-1);
    cout<<"To get from "<<startrow<<startcolumn<<" to "<<endrow<<endcolumn<<
" takes "<<des[(endrow-97)*8+endcolumn-1]<<" knight moves."<<endl;
    delete []des;
   }
 delete []source;
 return 0;
}
--

                    为了民族的尊严    为了祖国的明天

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.228]