6_8.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int clck[16];
int button[10][5] = {
    {0,1,2,-1,-1},{3,7,9,11,-1},{4,10,14,15,-1},{0,4,5,6,7},{6,7,8,10,12},{0,2,14,15,-1},{3,14,15,-1,-1},{4,5,7,14,15},{1,2,3,4,5},{3,4,5,9,13}    //연결된 스위치
    };
int ans;
 
void push(int n ,int cnt)
{
    bool finished = true;
 
    for (int i = 0; i < 16; i++)
    {
        if (clck[i] % 12 != 0)                
        {
            finished = false;
            break;
        }
    }
 
    if (finished)
    {
        ans = min(ans, cnt);                    
        return;
    }
 
    if (ans <= cnt) 
    {
        return;
    }
 
    if (!finished && n==10)                         
    {
        return;
    }
 
    for (int i = 0; i < 4; i++)            
    {
        for (int j = 0; j < 5; j++)
        {
            if (button[n][j] != -1)
            {
                clck[button[n][j]] += 3*i;       
            }
        }
 
        push(n + 1,cnt + i);                    
 
        for (int j = 0; j < 5; j++)
        {
            if (button[n][j] != -1)
            {
                clck[button[n][j]] -= 3*i;
            }
        }
 
    }
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        ans = 987654321;
 
        for (int i = 0; i < 16; i++)
        {
            cin >> clck[i];
        }
 
        push(0,0);
 
        if (ans == 987654321)                    
        {
            ans = -1;
        }
 
        cout << ans << endl;
    }
 
    return 0;
}