URAL1016[A Cube on the Walk]

变态的最短路,害我写了很多行。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-16


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


struct Cube


{


       int left,right,top,forward,bottom,backward;


       inline


       void swap(int& a,int& b,int& c,int& d)


       {


            int s=a;


            a=b;


            b=c;


            c=d;


            d=s;


       }


       inline


       void goup()


       {


            swap(bottom,backward,top,forward);


       }


       inline


       void godown()


       {


            swap(bottom,forward,top,backward);


       }


       inline


       void goright()


       {


            swap(bottom,right,top,left);


       }


       inline


       void goleft()


       {


            swap(bottom,left,top,right);


       }


};


struct Compare


{


       bool operator()(const pair<pair<Cube,pair<int,int> >,int>& a,


                       const pair<pair<Cube,pair<int,int> >,int>& b)


       {


            return a.second>b.second;


       }


};


 


class Application


{


      static const int SIDE=6;


      static const int top=0,


                       bottom=SIDE-1-top,


                       left=1,


                       right=SIDE-1-left,


                       forward=2,


                       backward=SIDE-1-forward;


      static const int SIZE=8;


      static const int ID=24;


      static const int oo=1<<29;


      pair<int,int> f,t;


      vector<int> get_point;


      vector<vector<int> > get_id;


      public:


      Application()


                   :get_point(SIDE),get_id(SIDE,vector<int>(SIDE))


      {


                    char x,y;


                    cin>>x>>y;


                    f.first=x-‘a’;


                    f.second=y-‘1’;


                    cin>>x>>y;


                    t.first=x-‘a’;


                    t.second=y-‘1’;


                    //forward, backward, top, right, bottom and left


                    cin>>get_point[forward]


                       >>get_point[backward]


                       >>get_point[top]


                       >>get_point[right]


                       >>get_point[bottom]


                       >>get_point[left];


      }


      int run()


      {


          //init get_id


          for (int i=0,id=0;i<SIDE;i++)


              for (int j=0;j<SIDE;j++)


                  if ((j!=i)&&(j+i+1!=SIDE))


                     get_id[i][j]=id++;


         


          //dijkstra


          typedef pair<pair<int,int>,int> pre_type;


          vector<vector<vector<int> > >


          dist(SIZE,vector<vector<int> >(SIZE,vector<int>(ID,oo)));


          vector<vector<vector<pre_type> > >


          pre(SIZE,vector<vector<pre_type> >(SIZE,vector<pre_type>(ID)));


         


          std::priority_queue<pair<pair<Cube,pair<int,int> >,int>,


                              vector<pair<pair<Cube,pair<int,int> >,int> >,


                              Compare> q;


          //push start state


          Cube start;


          start.top=top;


          start.bottom=bottom;


          start.left=left;


          start.right=right;


          start.forward=forward;


          start.backward=backward;


          q.push(make_pair(make_pair(start,f),get_point[start.bottom]));


         


          while (!q.empty())


          {


                pair<pair<Cube,pair<int,int> >,int> now=q.top();


                #define getdist(who) (dist[who.first.second.first]\


                                          [who.first.second.second]\


                                          [get_id[who.first.first.top]\


                                                 [who.first.first.left]]\


                                     )


               


                if (getdist(now)==oo)


                {


                   getdist(now)=now.second;


                   #define assignpre(dir,dx,dy)\


                   from.first.first=now.first.first;\


                   from.first.first.go##dir();\


                   from.first.second=make_pair(now.first.second.first+(dx),\


                                               now.first.second.second+(dy));\


                   if ((from.first.second.first>=0)\


                       &&(from.first.second.first<SIZE)\


                       &&(from.first.second.second>=0)\


                       &&(from.first.second.second<SIZE)\


                       &&(getdist(from)+get_point[now.first.first.bottom]==now.second))\


                   {\


                       pre[now.first.second.first]\


                          [now.first.second.second]\


                          [get_id[now.first.first.top]\


                                 [now.first.first.left]]\


                       =make_pair(from.first.second,\


                                  get_id[from.first.first.top]\


                                        [from.first.first.left]\


                                 );\


                   }


                   pair<pair<Cube,pair<int,int> >,int> from;


                   assignpre(left,-1,0);


                   assignpre(right,1,0);


                   assignpre(up,0,1);


                   assignpre(down,0,-1);                  


                   #undef assignpre


                  


                   #define letusgo(dir,dx,dy)\


                   go.first.first=now.first.first;\


                   go.first.first.go##dir();\


                   go.first.second=make_pair(now.first.second.first+(dx),\


                                             now.first.second.second+(dy));\


                   if ((go.first.second.first>=0)\


                       &&(go.first.second.first<SIZE)\


                       &&(go.first.second.second>=0)\


                       &&(go.first.second.second<SIZE)\


                       &&(getdist(go)==oo))\


                   {\


                      go.second=now.second+get_point[go.first.first.bottom];\


                      q.push(go);\


                   }


                   pair<pair<Cube,pair<int,int> >,int> go;


                   letusgo(left,-1,0);


                   letusgo(right,1,0);


                   letusgo(up,0,1);


                   letusgo(down,0,-1);


                   #undef letusgo


                }


                if (now.first.second==t) break;


                q.pop();


                #undef getdist


          }


          stack<pre_type> s;


          s.push(make_pair(q.top().first.second,


                           get_id[q.top().first.first.top]


                                 [q.top().first.first.left]));


          for (pre_type from=make_pair(f,get_id[start.top][start.left]);


               s.top()!=from;)


          {


              pre_type getpre=pre[s.top().first.first]


                        [s.top().first.second]


                        [s.top().second];


              s.push(getpre);


          }


          cout<<q.top().second<<” “;


          while (!s.empty())


          {


                cout<<char(s.top().first.first+’a’)


                    <<char(s.top().first.second+’1′);


                s.pop();


                if (s.empty()) cout<<endl;


                else cout<<” “;


          }


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}