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();

}