CLOCKSYNC

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

algospot.com :: CLOCKSYNC

 

각각의 스위치들과 연결된 시계가 있다. 스위치를 누를때마다 시간이 3시간 흐른다. (12->3->6->9)

이 때 모든 시계를 12시로 돌리기 위해 스위치를 최소 몇 번 눌러야 할지 계산해야한다.

먼저 스위치를 4번 누르면 다시 원상태로 돌아온다. 그러므로 스위치를 안 누르거나 최대 3번 누르는 것으로 한정시킬 수 있다.

스위치가 10개 있으므로 전체 경우의 수는 4^10이고 이는 완전 탐색으로 해결할 수 있다.

 

clocks : 현재 시계들의 상태

linked[i][j] : i번 스위치와 j번 시계가 연결되어 있으면 1, 그렇지 않으면 0

solve(swtch) : swtch는 이번에 누를 스위치 번호를 의미한다. 0번부터 9번까지 차례대로 최대 3번 누르면 된다. 코드 상으로는 push가 총 4번 호출되므로 다시 원상태로 돌아오게 된다.

 

#include <cstdio>
#include <algorithm>
#define INF 987654321
using namespace std;

int t,clocks[16];
char linked[10][17]={
    "1110000000000000",
    "0001000101010000",
    "0000100000100011",
    "1000111100000000",
    "0000001110101000",
    "1010000000000011",
    "0001000000000011",
    "0000110100000011",
    "0111110000000000",
    "0001110001000100"
};

bool check()
{
    for(int i=0;i<16;i++)
        if(clocks[i]!=12)
            return false;
    return true;
}

void push(int swtch)
{
    for(int clock=0;clock<16;clock++)
    {
        if(linked[swtch][clock]=='1')
        {
            clocks[clock]+=3;
            if(clocks[clock]==15) clocks[clock]=3;
        }
    }
}

int solve(int swtch)
{
    if(swtch==10) return check()?0:INF;
    int ret=INF;
    for(int cnt=0;cnt<4;cnt++)
    {
        ret=min(ret,cnt+solve(swtch+1));
        push(swtch);
    }
    return ret;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<16;i++)
            scanf("%d",&clocks[i]);
        int ans=solve(0);
        printf("%d\n",ans!=INF?ans:-1);
    }
    return 0;
}