URAL 1016 Cube on the Walk

URAL_1016
입방체가 같은 점에 있을 때 서로 다른 형태가 있을 수 있기 때문에 서로 다른 결과가 있을 수 있기 때문에 우리는 입방체의 형태에 따라 바둑판의 한 점을 몇 개의 점으로 나누어 최단로를 만들면 된다.물론 상태가 비교적 복잡하기 때문에 해시표로 각 점의 저장 위치를 비출 수 있다.

#include<stdio.h>

#include<string.h>

#define MAXD 1000010

#define Q 1000000

#define HASH 1000003

#define INF 0x3f3f3f3f

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

}

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;

}