2005百度之星程序设计大赛总决赛题目及解答

   /****************************************************************************************   
   2005百度之星程序设计大赛总决赛题目     
   八方块移动游戏要求从一个含8个数字（用1－8表示）的方块以及一个空格方块（用0表示）   
   的3×3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定   
   义的目标状态，空格方块在中间位置时，有上、下、左、右4个方向可移动，在四个角落上有   
   2个方向可移动，在其它位置上有3个方向可移动。例如，假设一个3×3矩阵的   
   初始状态为：　　　　　　　　　　　　　　   
   8 0 3         
   2 1 4         
   7 6 5   
   目标状态为：   
   1    2 3         
   8    0 4         
   7    6 5   
   则一个合法的移动路径为：   
   8，0，3，8，1，3，8，1，3，0，1，3，1，0，3，1，2，3   
   2，1，4，2，0，4，0，2，4，8，2，4，8，2，4，8，0，4   
   7，6，5，7，6，5，7，6，5，7，6，5，7，6，5，7，6，5   
   另外在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；   
   在上面例子中最短路径为5，如果不存在从初始状态的任何路径，则称该组状态无解。   
   请设计算法找到从八方块的某初始状态到某目标状态的所有可能路径中的最短路径，并用C/C＋＋实现。   
   输入数据程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态这两个文   
   件都由9个数字组成（0表示空格，1－8表示8个数字方块），每行3个数字，数字之间用空格隔开。   
   假定start.txt和goal.txt不会相同。   
   输出数据：如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出－1。   
   请在数字输出后再输出一回车换行符。   
   如果用　　　　　　　　　　　　     
   7 8 4         
   3 5 6         
   1 0 2   
   替换上面的start.txt则输出21。     
   如果用　　　　　　　　　　　　     
   7 5 2         
   0 6 3         
   4 1 8   
   替换上面的start.txt则输出－1。     
   程序在P42.8G的Linux机器上运行出正确结果不能超过10秒。   
    ****************************************************************************************/   

// //        解答：////////////////////
   #include   
   #include"stack.h"   
   extern    const    char    *start="start.txt";   
   extern    const    char    *goal="goal.txt";   
   const    int    M=200;   
   stack    process(10000);   
   int    _0[2]={1,3};   
   int    _1[3]={0,2,4};   
   int    _2[2]={1,5};   
   int    _3[2]={0,4};   
   int    _4[4]={1,3,5,7};   
   int    _5[3]={2,4,8};   
   int    _6[2]={3,7};   
   int    _7[3]={4,6,8};   
   int    _8[2]={5,7};   
   int    compare(int    begin[],int    end[])   
   {   
   for(int    i=0;i<9;i++)   
   {   
   if(begin[i]!=end[i])return    0;   
   }   
   return    1;   
   }   
   void    swap(int    &a,int    &b)   
   {   
   int    c;   
   c=a;a=b;b=c;   
   }   
   void    judgeable(int    position,int    &number)   
   {   
   //cout<   //cout<   //cout<   int    i=0;   
   switch(position)   
   {   
   case    0:   
   for(i=0;i<2;i++)   
   if(number<_0[i]&&_0[i]!=process.ReadTopSecond())   
   {   
   number=_0[i];   
   break;   
   }   
   break;   
   case    1:   
   for(i=0;i<3;i++)   
   if(number<_1[i]&&_1[i]!=process.ReadTopSecond())   
   {   
   number=_1[i];   
   break;   
   }   
   break;   
   case    2:   
   for(i=0;i<2;i++)   
   if(number<_2[i]&&_2[i]!=process.ReadTopSecond())   
   {   
   number=_2[i];   
   break;   
   }   
   break;   
   case    3:   
   for(i=0;i<2;i++)   
   if(number<_3[i]&&_3[i]!=process.ReadTopSecond())   
   {   
   number=_3[i];   
   break;   
   }   
   break;   
   case    4:   
   for(i=0;i<4;i++)   
   if(number<_4[i]&&_4[i]!=process.ReadTopSecond())   
   {   
   number=_4[i];   
   break;   
   }   
   break;   
   case    5:   
   for(i=0;i<3;i++)   
   if(number<_5[i]&&_5[i]!=process.ReadTopSecond())   
   {   
   number=_5[i];   
   break;   
   }   
   break;   
   case    6:   
   for(i=0;i<2;i++)   
   if(number<_6[i]&&_6[i]!=process.ReadTopSecond())   
   {   
   number=_6[i];   
   break;   
   }   
   break;   
   case    7:   
   for(i=0;i<3;i++)   
   if(number<_7[i]&&_7[i]!=process.ReadTopSecond())   
   {   
   number=_7[i];   
   break;   
   }   
   break;   
   case    8:   
   for(i=0;i<2;i++)   
   if(number<_8[i]&&_8[i]!=process.ReadTopSecond())   
   {   
   number=_8[i];   
   break;   
   }   
   break;   
   }   
   }   
   int    main()   
   {   
   ifstream    input_file;   
   int    begin[9],end[9],temp=-1,count=0;   
   int    judge[1000];   
   int    zero_position;   
   int    result=M;   
   int    countpath=0;   
   input_file.open(start);   
   if(!input_file)   
   {   
   cout<<"Can    not    open    start.txt    file!"<   return    1;   
   }   
   for(int    i=0;i<9;i++)   
   {   
   input_file>>begin[i];   
   if(begin[i]==0)zero_position=i;   
   }   
   input_file.close();   
   input_file.open(goal);   
   if(!input_file)   
   {   
   cout<<"Can    not    open    goal.txt    file!"<   return    1;   
   }   
   for(i=0;i<9;i++)input_file>>end[i];   
   input_file.close();   
   for(i=0;i<1000;i++)judge[i]=-1;   
   process.push(zero_position);   
   /*switch(zero_position)   
   {   
   case    0:judge[0]=1;   
   break;   
   case    1:judge[0]=0;   
   break;   
   case    2:judge[0]=1;   
   break;   
   case    3:judge[0]=0;   
   break;   
   case    4:judge[0]=1;   
   break;   
   case    5:judge[0]=2;   
   break;   
   case    6:judge[0]=3;   
   break;   
   case    7:judge[0]=4;   
   break;   
   case    8:judge[0]=5;   
   break;   
   }*///这段语句可有可无，因为在下面的换回语句里，begin[judge[count-1]]中的   
   //judge[count-1]在最后一个数弹出时process.ReadTop()＝－1；   
   count++;   
   for(int    j=0;;j++)   
   {   
   temp=judge[count];   
   judgeable(zero_position,judge[count]);   
   if(temp==judge[count])   
   {   
   out: process.pop();//弹出   
   swap(begin[process.ReadTop()],begin[judge[count-1]]);//换回来,还原   
   judge[count]=-1;   
   count--;   
   zero_position=process.ReadTop();   
   if(zero_position==-1)break;   
   }   
   else   
   {   
   process.push(judge[count]);//压入   
   swap(begin[zero_position],begin[judge[count]]);//交换   
                           zero_position=judge[count];   
   count++;   
   if(compare(begin,end))   
   {   
   if(result>count-1)   
   result=count-1;   
   countpath++;   
   cout<<"第"<   process.OutputAllData();   
   cout<<"共需："<   goto    out;   
   }   
   if(count-1>=result)goto    out;   
   }   
   }   
   cout<<"循环次数："<   if(result==M)cout<<"无解！"<   else    cout<<"最短路径为："<   return    1;   
   }   
   stack.h   
   #include   
   #include   
   templateclass    stack   
   {   
   public:   
   stack(int=10);   
   ~stack(){delete[]    elements;}   
   void    push(const    Type&    item);   
   Type    pop();   
   Type    GetTop();   
   Type    ReadTopSecond();   
   Type    ReadTop();   
   void    OutputAllData();   
   void    MakeEmpty(){top=-1;}   
   int    IsEmpty()const{return    top==-1;}   
   int    IsFull()const{return    top==maxSize-1;}   
   private:   
   int    top;   
   Type    *elements;   
   int    maxSize;   
   };   
   templatestack::stack(int    s):top(-1),maxSize(s)   
   {   
   elements=new    Type[maxSize];   
   assert(elements!=0);   
   }   
   templatevoid    stack::push(const    Type&    item)   
   {   
    
   assert(!IsFull());   
   //cout<<"压入："<   elements[++top]=item;   
   }   
   templateType    stack::pop()   
   {   
    
   assert(!IsEmpty());   
   //cout<<"弹出："<   return    elements[top--];   
   }   
   templateType    stack::GetTop()   
   {   
   assert(!IsEmpty());   
   return    elements[top];   
   }   
   templateType    stack::ReadTopSecond()   
   {   
   if(top-1<0)return    -1;   
   else    return    elements[top-1];   
   }   
   templateType    stack::ReadTop()   
   {   
   if(top<0)return    -1;   
   else return    elements[top];   
   }   
   templatevoid    stack::OutputAllData()   
   {   
   for(int    i=0;i<=top;i++)   
   {   
   cout<   if(i";   
   }   
   //cout<   }   
//////////////这就是全部的源程序了