usacoprac/clock.cpp at main · Resetz/usacoprac · GitHub

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
94
95
96
97
/*
1        1 2 4 5
2        1 2 3
3        2 3 5 6
4        1 4 7
5        2 4 5 6 8
6        3 6 9
7        4 5 7 8
8        7 8 9
9        5 6 8 9
*/

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

vector<int> v[10] {
    {1,2,4,5},
    {1,2,3},
    {2,3,5,6},
    {1,4,7},
    {2,4,5,6,8},
    {3,6,9},
    {4,5,7,8},
    {7,8,9},
    {5,6,8,9}
};

set<vector<int>> sv;
vector<int> current;

typedef struct node {
    vector<int> s;
    vector<int> moves;
    int t;
} node_t;


int main() {
    vector<int> r;
    current.resize(9);
    for (int i = 0 ; i < 9; i++) {
        int x;
        cin >> x;
        x = (x/3) % 4;
        current[i] = x;
    }

    queue<node_t> q;
    node_t o;
    o.s = current;
    o.t = 0;
    q.push(o);
    while (!q.empty()) {
        o = q.front();
        q.pop();

        bool good = true;
        for (int i = 0 ; i < 9 ; i++) {
            if (o.s[i] != 0) {
                good = false;
            }
        }
        if (good) {
            for (int i = 0; i < o.t; i++) {
                cout << o.moves[i] << " ";
            }
            return 0;
        }

        o.t++;
        for (int i = 0 ; i < 9 ; i++) {
            for (int j = 0 ; j < v[i].size(); j++) {
                o.s[v[i][j]-1] = (o.s[v[i][j]-1] + 1) % 4;
            }
            if (sv.insert(o.s).second) {
                o.moves.push_back(i+1);
                q.push(o);
                o.moves.pop_back();
            }
            for (int j = 0 ; j < v[i].size(); j++) {

                o.s[v[i][j]-1] = (o.s[v[i][j]-1] - 1);
                if (o.s[v[i][j]-1] < 0) {
                    o.s[v[i][j]-1] = 3;
                }
            }
        }
    }


}