#include #include #include #include #include using namespace std; #define FRONT 0 #define BACK 1 #define TOP 2 #define RIGHT 3 #define BOTTOM 4 #define LEFT 5 #define NIL (-1) class State { public: static State unserialize( int n ) { State result; result.left = n % 6, n /= 6; result.top = n % 6, n /= 6; result.front = n % 6, n /= 6; result.col = n % 8, n /= 8; result.row = n % 8; return result; } static int serialize( const State &s ) { return (((s.row*8 + s.col)*6 + s.front)*6 + s.top)*6 + s.left; } static State makeInit( int row, int col ) { State result; result.row = row; result.col = col; result.front = FRONT; result.top = TOP; result.left = LEFT; return result; } public: // left bottom = (0, 0), right top = (height-1, width-1). int row, col, front, top, left; bool isValidPosition() { return (row >= 0 && row < 8 && col >= 0 && col < 8); } int getBottom() { if ( front == BOTTOM ) return FRONT; if ( top == BOTTOM ) return TOP; if ( left == BOTTOM ) return LEFT; if ( front == TOP ) return BACK; if ( top == TOP ) return BOTTOM; if ( left == TOP ) return RIGHT; } void rotate( int i ) { switch ( i ) { case 0: rotateFront(); break; case 1: rotateBack(); break; case 2: rotateLeft(); break; case 3: rotateRight(); break; } } void rotateFront() { row--; front = nextAtRotateFront(front); top = nextAtRotateFront(top); left = nextAtRotateFront(left); } void rotateBack() { row++; for ( int i = 0; i < 3; i++ ) front = nextAtRotateFront(front), top = nextAtRotateFront(top), left = nextAtRotateFront(left); } void rotateLeft() { col--; front = nextAtRotateLeft(front); top = nextAtRotateLeft(top); left = nextAtRotateLeft(left); } void rotateRight() { col++; for ( int i = 0; i < 3; i++ ) front = nextAtRotateLeft(front), top = nextAtRotateLeft(top), left = nextAtRotateLeft(left); } private: int nextAtRotateFront( int n ) { switch ( n ) { case FRONT: return BOTTOM; case BACK: return TOP; case TOP: return FRONT; case RIGHT: return RIGHT; case BOTTOM: return BACK; case LEFT: return LEFT; } } int nextAtRotateLeft( int n ) { switch ( n ) { case FRONT: return FRONT; case BACK: return BACK; case TOP: return LEFT; case RIGHT: return TOP; case BOTTOM: return RIGHT; case LEFT: return BOTTOM; } } }; int F[6]; void printPath( int final, int cost, map &PREV ) { vector path; for ( int s = final; s != NIL; s = PREV[s] ) path.push_back(s); reverse(path.begin(), path.end()); cout << cost; for ( int i = 0; i < path.size(); i++ ) { State s = State::unserialize(path[i]); cout << ' ' << (char)(s.col+'a') << s.row+1; } cout << endl; } void compute( int initRow, int initCol, int finalRow, int finalCol ) { State init = State::makeInit(initRow, initCol); multimap PQ; map PREV; map D; PQ.insert(make_pair(F[BOTTOM], State::serialize(init))); PREV.insert(make_pair(State::serialize(init), NIL)); D.insert(make_pair(State::serialize(init), F[BOTTOM])); while ( !PQ.empty() ) { const int d = PQ.begin()->first; State s = State::unserialize(PQ.begin()->second); PQ.erase(PQ.begin()); if ( D[State::serialize(s)] < d ) continue; if ( s.row == finalRow && s.col == finalCol ) { printPath(State::serialize(s), d, PREV); return; } for ( int i = 0; i < 4; i++ ) { State t = s; t.rotate(i); if ( !t.isValidPosition() ) continue; const int serial = State::serialize(t); const int nd = d + F[t.getBottom()]; if ( PREV.find(serial) == PREV.end() || D[serial] > nd ) { PQ.insert(make_pair(nd, serial)); PREV[serial] = State::serialize(s); D[serial] = nd; } } } assert( false ); } int main() { char initCol, initRow, finalCol, finalRow; cin >> initCol >> initRow >> finalCol >> finalRow; cin >> F[FRONT] >> F[BACK] >> F[TOP] >> F[RIGHT] >> F[BOTTOM] >> F[LEFT]; compute(initRow-'1', initCol-'a', finalRow-'1', finalCol-'a'); return 0; }