/* @JUDGE_ID: 32472GK 1016 C++ */ #include #include #include #include #include #include using namespace std; struct dice { int forward, backward, top, bottom, left, right; }; dice move_left_dice(dice& d) { dice e = {d.forward, d.backward, d.left, d.right, d.top, d.bottom}; return e; } dice move_right_dice(dice& d) { dice e = {d.forward, d.backward, d.right, d.left, d.bottom, d.top}; return e; } dice move_forward_dice(dice& d) { dice e = {d.bottom, d.top, d.forward, d.backward, d.right, d.left}; return e; } dice move_backward_dice(dice& d) { dice e = {d.top, d.bottom, d.backward, d.forward, d.right, d.left}; return e; } typedef int len_t; struct vert { dice dice; int pos; }; bool operator <(const vert& lhs, const vert& rhs) { #define cmp(mmb) \ if(lhs.mmb != rhs.mmb) { return lhs.mmb < rhs.mmb; } cmp(pos); cmp(dice.forward); cmp(dice.backward); cmp(dice.top); cmp(dice.left); cmp(dice.right); cmp(dice.bottom); return false; } struct cedge { vert from, to; len_t dist; cedge(vert from, vert to, len_t dist) : from(from), to(to), dist(dist) {} cedge() {} }; bool operator<(const cedge& a, const cedge& b) { return a.dist > b.dist; } len_t dijkstra(const vert src, int dst, vert& redst, map& prev) { map shtstlen; priority_queue Q; Q.push(cedge(src, src, src.dice.bottom)); while (!Q.empty()) { cedge c = Q.top(); Q.pop(); if (shtstlen.count(c.to)) { continue; } shtstlen[c.to] = c.dist; prev[c.to] = c.from; if (c.to.pos == dst) { redst = c.to; return c.dist; } { int pos = c.to.pos; vert v; int x = pos / 8; int y = pos % 8; if (x - 1 >= 0) { v.pos = (x - 1) * 8 + y; v.dice = move_left_dice(c.to.dice); Q.push(cedge(c.to, v, c.dist + v.dice.bottom)); } if (y - 1 >= 0) { v.pos = x * 8 + (y - 1); v.dice = move_backward_dice(c.to.dice); Q.push(cedge(c.to, v, c.dist + v.dice.bottom)); } if (x + 1 < 8) { v.pos = (x + 1) * 8 + y; v.dice = move_right_dice(c.to.dice); Q.push(cedge(c.to, v, c.dist + v.dice.bottom)); } if (y + 1 < 8) { v.pos = x * 8 + (y + 1); v.dice = move_forward_dice(c.to.dice); Q.push(cedge(c.to, v, c.dist + v.dice.bottom)); } } } return -1; } void solve(int src, int dst, dice d) { vert v = { d, src }; map prev; vert redst; len_t len = dijkstra(v, dst, redst, prev); cout << len; deque q; do { q.push_front(redst); assert(prev.count(redst)); redst = prev[redst]; } while(redst < v || v < redst); q.push_front(redst); for (int i = 0; i < q.size(); ++i) { cout << ' '; cout << char(q[i].pos / 8 + 'a') << (q[i].pos % 8 + 1); } cout << endl; } int main() { string str1, str2; dice d; cin >> str1 >> str2; int src = (str1[0] - 'a') * 8 + str1[1] - '1'; int dst = (str2[0] - 'a') * 8 + str2[1] - '1'; cin >> d.forward >> d.backward >> d.top >> d.right >> d.bottom >> d.left; solve(src, dst, d); }