Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <ctime>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <deque>
- #include <map>
- #include <set>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define sz(x) ((int)(x).size())
- #define TASKNAME "cube"
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- typedef unsigned int hash;
- const int actions[15][24] = {
- {5,13,1,9,64,68,24,28,16,20,40,44,32,36,56,60,48,52,72,76,80,84,88,92},
- {11,3,15,7,32,36,24,28,48,52,40,44,64,68,56,60,16,20,72,76,80,84,88,92},
- {32,4,40,12,21,29,17,25,80,36,88,44,48,52,56,60,64,10,72,2,78,84,70,92},
- {78,4,70,12,27,19,31,23,0,36,8,44,48,52,56,60,64,90,72,82,32,84,40,92},
- {0,4,49,57,16,13,24,9,37,45,33,41,85,52,81,60,64,68,72,76,21,29,88,92},
- {0,4,31,23,16,83,24,87,43,35,47,39,11,52,15,60,64,68,72,76,59,51,88,92},
- {0,74,8,66,16,20,24,28,32,4,40,12,53,61,49,57,94,68,86,76,80,36,88,44},
- {0,36,8,44,16,20,24,28,32,84,40,92,59,51,63,55,14,68,6,76,80,74,88,66},
- {27,19,8,12,91,20,95,28,32,36,40,44,48,3,56,7,69,77,65,73,80,84,63,55},
- {53,61,8,12,5,20,1,28,32,36,40,44,48,93,56,89,75,67,79,71,80,84,17,25},
- {0,4,8,12,16,20,40,44,32,36,56,60,48,52,72,76,64,68,24,28,85,93,81,89},
- {0,4,8,12,16,20,72,76,32,36,24,28,48,52,40,44,64,68,56,60,91,83,95,87},
- {11,3,15,7,32,36,40,44,48,52,56,60,64,68,72,76,16,20,24,28,85,93,81,89},
- {32,36,40,44,21,29,17,25,80,84,88,92,59,51,63,55,14,10,6,2,78,74,70,66},
- {0,4,49,57,16,13,24,9,37,45,33,41,85,52,81,60,64,68,72,76,21,29,88,92}
- };
- class Cube {
- public:
- char st[24];
- private:
- static char gbuf[16][5];
- static const char* sufs;
- hash ch;
- static const char* get(int x) {
- if (x == -2) return "G";
- if (x == -1) return ".";
- if (gbuf[x][0]) return gbuf[x];
- int len = 0;
- gbuf[x][len++] = 'a' + (x >> 2);
- if (x & 3)
- gbuf[x][len++] = sufs[x & 3];
- gbuf[x][len] = 0;
- return gbuf[x];
- }
- /*
- char:
- -2: green
- -1: red
- 0..3: a (a, a+, a$, a-)
- 4..7: b (b, b+, b$, b-)
- 8..11: c (c, c+, c$, c-)
- 12..15: d (d, d+, d$, d-)
- */
- int turnElem(int a, int x) {
- if (a < 0) return a;
- int cx = (a) & 3;
- int nx = (cx + x) & 3;
- return a + nx - cx;
- }
- void perform(int id) {
- char nst[24];
- for (int i = 0; i < 24; i++) {
- int stid = actions[id][i] >> 2;
- int x = actions[id][i] & 3;
- nst[i] = turnElem(st[stid], x);
- }
- memcpy(st, nst, sizeof nst);
- }
- public:
- Cube() {
- memset(st, -1, sizeof st);
- for (int i = 0; i < 4; i++) {
- st[4 + i] = -2;
- st[20 + i] = 4 * i;
- }
- recalc();
- }
- Cube(const char f[6][100]) {
- const int data[6][8] = {
- { 0, 1, -1, -1, -1, -1, -1, -1 },
- { 2, 3, -1, -1, -1, -1, -1, -1 },
- { 4, 5, 8, 9, 12, 13, 16, 17 },
- { 6, 7, 10, 11, 14, 15, 18, 19 },
- { 20, 21, -1, -1, -1, -1, -1, -1 },
- { 22, 23, -1, -1, -1, -1, -1, -1 },
- };
- for (int y = 0; y < 6; y++) {
- string s = f[y];
- for (int x = 0; x < 8 && data[y][x] >= 0; x++) {
- char &res = st[data[y][x]];
- char c = s[0]; s = string(s, 1);
- if (c == 'G') res = -2;
- else if (c == '.') res = -1;
- else {
- int x = (c - 'a') << 2;
- if (s.length() > 0 && strchr(sufs, s[0])) {
- x += strchr(sufs, s[0]) - sufs;
- s = string(s, 1);
- }
- res = x;
- }
- }
- }
- recalc();
- }
- void recalc() { ch = getHash(); }
- void rollLeft() { perform(12); }
- void rollTop() { perform(13); }
- void turnFront() { perform(14); }
- void turn(int side, int k) { perform(2 * side + k); }
- hash getHash() {
- hash res = 0;
- for (int i = 0; i < 24; i++)
- res = res * 29 + st[i];
- return res;
- }
- void print() {
- eprintf(" %s%s\n", get(st[0]), get(st[1]));
- eprintf(" %s%s\n", get(st[2]), get(st[3]));
- for (int i = 1; i <= 4; i++)
- for (int i2 = 0; i2 < 2; i2++)
- eprintf("%s", get(st[i * 4 + i2]));
- eprintf("\n");
- for (int i = 1; i <= 4; i++)
- for (int i2 = 2; i2 < 4; i2++)
- eprintf("%s", get(st[i * 4 + i2]));
- eprintf("\n");
- eprintf(" %s%s\n", get(st[20]), get(st[21]));
- eprintf(" %s%s\n", get(st[22]), get(st[23]));
- }
- bool operator==(const Cube &c) const { return !memcmp(st, c.st, sizeof st); }
- bool operator!=(const Cube &c) const { return memcmp(st, c.st, sizeof st); }
- bool operator<(const Cube &c) const {
- if (ch != c.ch) return ch < c.ch;
- return memcmp(st, c.st, sizeof st) < 0;
- }
- };
- char Cube::gbuf[16][5];
- const char* Cube::sufs = " +$-";
- hash needh;
- int ans;
- vector<pii> ops;
- set<hash> was;
- clock_t end;
- bool go(Cube c, int pr = -1, int dep = 0) {
- hash h = c.getHash();
- if (h == needh) return true;
- if (dep >= ans) return false;
- if (was.count(h)) return false;
- if (clock() >= end) return false;
- was.insert(h);
- for (int i = 0; i < 6; i++) if (i != pr)
- for (int i2 = 0; i2 < 2; i2++) {
- Cube c2 = c;
- c2.turn(i, i2);
- if (go(c2, i, dep + 1)) {
- ops.pb(mp(i, i2));
- return true;
- }
- }
- return false;
- }
- vector<pii> restore(map<Cube, int> &fr, Cube c) {
- vector<pii> res;
- eprintf("restore\n");
- c.print();
- for (int step = 0;; step++) {
- assert(fr.count(c));
- const int cfr = fr[c];
- if (cfr < 0) break;
- res.pb(mp(cfr >> 1, (cfr & 1)));
- c.turn(cfr >> 1, !(cfr & 1)); c.recalc();
- }
- reverse(res.begin(), res.end());
- return res;
- }
- char f[6][100];
- int main() {
- end = clock() + CLOCKS_PER_SEC * 1.8;
- needh = Cube().getHash();
- freopen(TASKNAME ".in", "r", stdin);
- freopen(TASKNAME ".out", "w", stdout);
- while (scanf("%s", f[0]) >= 1) {
- for (int i = 1; i < 6; i++)
- scanf("%s", f[i]);
- Cube c(f), c2;
- map<Cube, int> fr, fr2;
- for (int step = 0; step < 2; step++) {
- deque<pair<Cube, int> > q;
- fr[c] = -1;
- q.pb(mp(c, 0));
- while (!q.empty()) {
- Cube c = q.front().first;
- int d = q.front().second;
- q.pop_front();
- if (fr2.count(c)) {
- assert(step == 1);
- vector<pii> ops = restore(fr2, c), ops2 = restore(fr, c);
- reverse(ops2.begin(), ops2.end());
- for (int i = 0; i < sz(ops); i++)
- printf("%c%c\n", "BLURDF"[ops[i].first], "+-"[ops[i].second]);
- for (int i = 0; i < sz(ops2); i++)
- printf("%c%c\n", "BLURDF"[ops2[i].first], "+-"[!ops2[i].second]);
- goto end;
- }
- if (d >= 6 || (step == 1 && d >= 5)) continue;
- for (int i = 0; i < 6; i++)
- for (int i2 = 0; i2 < 2; i2++) {
- Cube c2 = c;
- c2.turn(i, i2);
- c2.recalc();
- if (fr.count(c2)) continue;
- fr[c2] = i * 2 + i2;
- q.pb(mp(c2, d + 1));
- }
- }
- swap(c, c2);
- fr.swap(fr2);
- }
- printf("NO SOLUTION\n");
- end:;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment