URAL_1016

    由于立方体位于同一个点时可能有不同的形态，从而有不同的结果，因此我们可以根据立方体的形态将棋盘上一个点拆成若干个点，然后做最短路即可。当然，由于状态比较复杂，可以用哈希表映射出每个点的存储位置。

#include
     
      #include
      
       #define MAXD 1000010#define Q 1000000#define HASH 1000003#define INF 0x3f3f3f3fint dx[] = {-1, 1, 0, 0}, dy[] = {
   0, 0, 1, -1};int ch[][6] = {
   {
   0, 1, 5, 2, 3, 4}, {
   0, 1, 3, 4, 5, 2}, {
   2, 4, 1, 3, 0, 5}, {
   4, 2, 0, 3, 1, 5}};char b[10];int sx, sy, tx, ty, qx[MAXD], qy[MAXD], st[MAXD][6], v[MAXD], where[MAXD];struct Hashmap{    int f[MAXD], head[HASH], next[MAXD], e, state[MAXD][6], x[MAXD], y[MAXD], p[MAXD];    void init()    {        memset(head, -1, sizeof(head));        e = 1;    }    int hash(int s)    {        int i, h, seed = 131;        h = qx[s] * seed + qy[s];        for(i = 0; i < 6; i ++)            h = h * seed + st[s][i];        return (h & 0x7fffffff) % HASH;    }    int push(int s, int fa)    {        int i, h = hash(s);        for(i = head[h]; i != -1; i = next[i])            if(x[i] == qx[s] && y[i] == qy[s] && memcmp(st[s], state[i], sizeof(state[i])) == 0)                break;        if(i == -1)        {            x[e] = qx[s], y[e] = qy[s], memcpy(state[e], st[s], sizeof(st[s])), f[e] = v[s];            p[e] = fa;            next[e] = head[h], head[h] = e;            return e ++;        }        if(v[s] < f[i])        {            f[i] = v[s], p[i] = fa;            return i;        }        return 0;    }}hm;void print(int cur){    if(hm.p[cur] != -1)        print(hm.p[cur]);    printf(" %c%c", hm.x[cur] + 'a', hm.y[cur] + '1');}void solve(){    int i, j, k, front, rear, x, y, newx, newy, ans = INF;    front = 0, rear = 1;    hm.init();    hm.push(0, -1);    while(front != rear)    {        x = qx[front], y = qy[front];        for(i = 0; i < 4; i ++)        {            newx = x + dx[i], newy = y + dy[i];            if(newx >= 0 && newx < 8 && newy >= 0 && newy < 8)            {                qx[rear] = newx, qy[rear] = newy;                for(j = 0; j < 6; j ++)                    st[rear][ch[i][j]] = st[front][j];                v[rear] = v[front] + st[rear][4];                if(k = hm.push(rear, where[front]))                {                    where[rear] = k;                    ++ rear;                    if(rear > Q)                        rear = 0;                }            }        }        ++ front;        if(front > Q)            front = 0;    }    for(i = 1; i < hm.e; i ++)        if(hm.x[i] == tx && hm.y[i] == ty && hm.f[i] < ans)            ans = hm.f[i], k = i;    printf("%d", ans);    print(k);    printf("\n");}int main(){    int i;    while(scanf("%s", b) == 1)    {        sx = b[0] - 'a', sy = b[1] - '1';        scanf("%s", b);        tx = b[0] - 'a', ty = b[1] - '1';        qx[0] = sx, qy[0] = sy;        for(i = 0; i < 6; i ++)            scanf("%d", &st[0][i]);        v[0] = st[0][4], where[0] = 1;        solve();    }    return 0;}