Algorithm/알고스팟

algospot - hanoi4

jhg0406 2020. 1. 17. 02:49
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//algospot - hanoi4
 
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int N;
int last, state;
int c[1 << 24];
 
int set(int base, int idx, int value)
{
    return (base & ~(3 << (idx*2))) | (value << (idx*2));
}
 
int get(int base, int idx)
{
    return 3 & (base >> (idx*2));
}
 
void init()
{
    cin >> N;
    int n, idx;
    int x = 0;
    last = state = 0;
    for(int i = 0; i<4; i++)
    {
        cin >> n;
        for(int j = 0; j<n; j++)
        {
            cin >> idx;
            state = set(state, idx-1, i);
            last = set(last, x++, 3);
        }
    }
}
 
int incr(int u)
{
    return u > 0 ? u+1 : u-1;
}
 
bool isEnd(int u, int v)
{
    return u*v < 0 ? true : false;
}
 
int bfs()
{
    if(state == last) return 0;
    queue<int> q;
    memset(c, 0, sizeof(c));
    c[state] = 1;
    q.push(state);
    c[last] = -1;
    q.push(last);
    int cost;
    while(true)
    {
        state = q.front(); q.pop();
        cost = c[state];
        int top[4] = {-1, -1, -1, -1};
        for(int i = N-1; i>=0; --i)
            top[get(state, i)] = i;
        for(int i = 0; i<4; i++)
            for(int j = 0; j<4; j++)
                if(i != j && top[i] != -1 && (top[j] == -1 || top[j] > top[i]))
                {
                    state = set(state, top[i], j);
                    if(isEnd(cost, c[state]))
                        return (cost > 0 ? cost : -1*cost) + (c[state] > 0 ? c[state] : -1*c[state]);
                    else if(c[state] == 0)
                    {
                        q.push(state);
                        c[state] = incr(cost);
                    }
                    state = set(state, top[i], i);
                }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int C; cin >> C;
    for(int t_num = 0; t_num < C; t_num++)
    {
        init();
        std::cout << bfs() -1 << "\n";
    }
}
 cs

 

 

https://algospot.com/judge/problem/read/HANOI4

 

algospot.com :: HANOI4

하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥에 모두 크기 순서대로 꽂혀 있습니다. 게임의 목적은 모든 원반을 맨 오른쪽 기둥으로 옮기는 것입니다. 원반을 움직일 때는 다음과 같은 규칙을 따라야 합니다. 한 번에 한 개의 원반만을 움직일 수 있습니다. 원반을 기둥이 아닌 다른 곳에 내려놓거나, 원반을 하나 들

algospot.com

 

 

 

Hanoi4

BFS 양방향 탐색 + 비트마스크 문제

원판이 어느 막대기에 꽃혀있는지에 대한 정보를 정점,

원판 하나를 옮겼을때 만들수 있는 상태들끼리 간선으로 연결하는 무향그래프를 만듭니다.

각각의 상태(원판이 어느 막대기에 꽃혀있는지에 대한 정보)는 비트마스크로 표현합니다!

BFS탐색은 시간이 초과되기 때문에 양방향 탐색을 사용합니다!