Playing with Wheels

https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1008 

Online Judge

성공여부 : 성공(Accept)

아이디어 : 큐를 사용한 모든 경로 검색 & Count를 증가하여 최소경로 탐색

(해답의 도움을 얻음)

추가 내용 :

이 문제에 대해 start지점과 end지점, 불가능한 지점을 모두 check한 뒤 start부터 4개의 트랙의 두 방향을 모두 진행한다. 가능한 Case에는 count값을 1 증가하고 queue에 넣어 다시금 검색을 할 수 있도록 진행한다. 도중에 불가능한 지점은 queue에 저장되지 않으므로 신경쓰지 않아도 된다.

그리고 4개의 트랙을 unite() 함수를 사용하여 queue와 map의 size를 최대한 줄여봤다.

 

#include <stdio.h>

int unite(int x, int y, int z, int k)
{
    return x * 1000 + y * 100 + z * 10 + k;
}

int main()
{

    int n, i;
    int map[10001]; // 0000~100000
    int x, y, z, k;
    int queue[10001];
    int top, bot;
    scanf("%d", &n);

    while (n--)
    {
        int start, end, l, p1, p2, p3, p4, count;
        int p1l, p1r, p2l, p2r, p3l, p3r, p4l, p4r;
        bot = 0;
        top = 1;
        for (i = 0; i < 10001; i++)
            map[i] = 0;

        scanf("%d %d %d %d", &x, &y, &z, &k);
        start = unite(x, y, z, k);
        map[start] = 1;
        queue[0] = start;

        scanf("%d %d %d %d", &x, &y, &z, &k);
        end = unite(x, y, z, k);

        scanf("%d", &l);
        while (l--)
        {
            scanf("%d %d %d %d", &x, &y, &z, &k);
            map[unite(x, y, z, k)] = -1;
        }
        // init

        while (top > bot && map[end] == 0)
        {
            int temp;
            temp = queue[bot++];
            count = map[temp];
            p1 = temp / 1000;
            temp = temp % 1000;
            p2 = temp / 100;
            temp = temp % 100;
            p3 = temp / 10;
            temp = temp % 10;
            p4 = temp;

            if (p1 == 0)
                p1l = 9;
            else
                p1l = p1 - 1;
            p1r = (p1 + 1) % 10;
            if (p2 == 0)
                p2l = 9;
            else
                p2l = p2 - 1;
            p2r = (p2 + 1) % 10;
            if (p3 == 0)
                p3l = 9;
            else
                p3l = p3 - 1;
            p3r = (p3 + 1) % 10;
            if (p4 == 0)
                p4l = 9;
            else
                p4l = p4 - 1;
            p4r = (p4 + 1) % 10;

            if (map[unite(p1l, p2, p3, p4)] == 0)
            {
                map[unite(p1l, p2, p3, p4)] = count + 1;
                queue[top++] = unite(p1l, p2, p3, p4);
            }
            if (map[unite(p1r, p2, p3, p4)] == 0)
            {
                map[unite(p1r, p2, p3, p4)] = count + 1;
                map[unite(p1r, p2, p3, p4)] = count + 1;
                queue[top++] = unite(p1r, p2, p3, p4);
            }
            if (map[unite(p1, p2l, p3, p4)] == 0)
            {
                map[unite(p1, p2l, p3, p4)] = count + 1;
                map[unite(p1, p2l, p3, p4)] = count + 1;
                queue[top++] = unite(p1, p2l, p3, p4);
            }
            if (map[unite(p1, p2r, p3, p4)] == 0)
            {
                map[unite(p1, p2r, p3, p4)] = count + 1;
                map[unite(p1, p2r, p3, p4)] = count + 1;
                queue[top++] = unite(p1, p2r, p3, p4);
            }
            if (map[unite(p1, p2, p3l, p4)] == 0)
            {
                map[unite(p1, p2, p3l, p4)] = count + 1;
                map[unite(p1, p2, p3l, p4)] = count + 1;
                queue[top++] = unite(p1, p2, p3l, p4);
            }
            if (map[unite(p1, p2, p3r, p4)] == 0)
            {
                map[unite(p1, p2, p3r, p4)] = count + 1;
                map[unite(p1, p2, p3r, p4)] = count + 1;
                queue[top++] = unite(p1, p2, p3r, p4);
            }
            if (map[unite(p1, p2, p3, p4l)] == 0)
            {
                map[unite(p1, p2, p3, p4l)] = count + 1;
                map[unite(p1, p2, p3, p4l)] = count + 1;
                queue[top++] = unite(p1, p2, p3, p4l);
            }
            if (map[unite(p1, p2, p3, p4r)] == 0)
            {
                map[unite(p1, p2, p3, p4r)] = count + 1;
                map[unite(p1, p2, p3, p4r)] = count + 1;
                queue[top++] = unite(p1, p2, p3, p4r);
            }
        }
        printf("%d\n", map[end] - 1);
    }
    return 0;
}