yeputons

Untitled

Mar 29th, 2012
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.17 KB | None | 0 0
  1. #include <cstdio>
  2. #include <ctime>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <string>
  9. #include <deque>
  10. #include <map>
  11. #include <set>
  12.  
  13. using namespace std;
  14.  
  15. #define pb push_back
  16. #define mp make_pair
  17. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  18. #define sz(x) ((int)(x).size())
  19. #define TASKNAME "cube"
  20.  
  21. typedef long long ll;
  22. typedef vector<ll> vll;
  23. typedef vector<int> vi;
  24. typedef vector<vi> vvi;
  25. typedef vector<bool> vb;
  26. typedef vector<vb> vvb;
  27. typedef pair<int, int> pii;
  28. typedef unsigned int hash;
  29.  
  30. const int actions[15][24] = {
  31.   {5,13,1,9,64,68,24,28,16,20,40,44,32,36,56,60,48,52,72,76,80,84,88,92},
  32.   {11,3,15,7,32,36,24,28,48,52,40,44,64,68,56,60,16,20,72,76,80,84,88,92},
  33.   {32,4,40,12,21,29,17,25,80,36,88,44,48,52,56,60,64,10,72,2,78,84,70,92},
  34.   {78,4,70,12,27,19,31,23,0,36,8,44,48,52,56,60,64,90,72,82,32,84,40,92},
  35.   {0,4,49,57,16,13,24,9,37,45,33,41,85,52,81,60,64,68,72,76,21,29,88,92},
  36.   {0,4,31,23,16,83,24,87,43,35,47,39,11,52,15,60,64,68,72,76,59,51,88,92},
  37.   {0,74,8,66,16,20,24,28,32,4,40,12,53,61,49,57,94,68,86,76,80,36,88,44},
  38.   {0,36,8,44,16,20,24,28,32,84,40,92,59,51,63,55,14,68,6,76,80,74,88,66},
  39.   {27,19,8,12,91,20,95,28,32,36,40,44,48,3,56,7,69,77,65,73,80,84,63,55},
  40.   {53,61,8,12,5,20,1,28,32,36,40,44,48,93,56,89,75,67,79,71,80,84,17,25},
  41.   {0,4,8,12,16,20,40,44,32,36,56,60,48,52,72,76,64,68,24,28,85,93,81,89},
  42.   {0,4,8,12,16,20,72,76,32,36,24,28,48,52,40,44,64,68,56,60,91,83,95,87},
  43.   {11,3,15,7,32,36,40,44,48,52,56,60,64,68,72,76,16,20,24,28,85,93,81,89},
  44.   {32,36,40,44,21,29,17,25,80,84,88,92,59,51,63,55,14,10,6,2,78,74,70,66},
  45.   {0,4,49,57,16,13,24,9,37,45,33,41,85,52,81,60,64,68,72,76,21,29,88,92}
  46. };
  47. class Cube {
  48.   public:
  49.   char st[24];
  50.   private:
  51.  
  52.   static char gbuf[16][5];
  53.   static const char* sufs;
  54.   hash ch;
  55.  
  56.   static const char* get(int x) {
  57.     if (x == -2) return "G";
  58.     if (x == -1) return ".";
  59.     if (gbuf[x][0]) return gbuf[x];
  60.     int len = 0;
  61.     gbuf[x][len++] = 'a' + (x >> 2);
  62.     if (x & 3)
  63.       gbuf[x][len++] = sufs[x & 3];
  64.     gbuf[x][len] = 0;
  65.     return gbuf[x];
  66.   }
  67.   /*
  68.     char:
  69.     -2: green
  70.     -1: red
  71.     0..3: a (a, a+, a$, a-)
  72.     4..7: b (b, b+, b$, b-)
  73.     8..11: c (c, c+, c$, c-)
  74.     12..15: d (d, d+, d$, d-)
  75.   */
  76.   int turnElem(int a, int x) {
  77.     if (a < 0) return a;
  78.     int cx = (a) & 3;
  79.     int nx = (cx + x) & 3;
  80.     return a + nx - cx;
  81.   }
  82.   void perform(int id) {
  83.     char nst[24];
  84.     for (int i = 0; i < 24; i++) {
  85.       int stid = actions[id][i] >> 2;
  86.       int x = actions[id][i] & 3;
  87.       nst[i] = turnElem(st[stid], x);
  88.     }
  89.     memcpy(st, nst, sizeof nst);
  90.   }
  91.  
  92.   public:
  93.   Cube() {
  94.     memset(st, -1, sizeof st);
  95.     for (int i = 0; i < 4; i++) {
  96.       st[4 + i] = -2;
  97.       st[20 + i] = 4 * i;
  98.     }
  99.     recalc();
  100.   }
  101.   Cube(const char f[6][100]) {
  102.     const int data[6][8] = {
  103.       {  0,  1, -1, -1, -1, -1, -1, -1 },
  104.       {  2,  3, -1, -1, -1, -1, -1, -1 },
  105.       {  4,  5,  8,  9, 12, 13, 16, 17 },
  106.       {  6,  7, 10, 11, 14, 15, 18, 19 },
  107.       { 20, 21, -1, -1, -1, -1, -1, -1 },
  108.       { 22, 23, -1, -1, -1, -1, -1, -1 },
  109.     };
  110.     for (int y = 0; y < 6; y++) {
  111.       string s = f[y];
  112.       for (int x = 0; x < 8 && data[y][x] >= 0; x++) {
  113.         char &res = st[data[y][x]];
  114.         char c = s[0]; s = string(s, 1);
  115.  
  116.         if (c == 'G') res = -2;
  117.         else if (c == '.') res = -1;
  118.         else {
  119.           int x = (c - 'a') << 2;
  120.           if (s.length() > 0 && strchr(sufs, s[0])) {
  121.             x += strchr(sufs, s[0]) - sufs;
  122.             s = string(s, 1);
  123.           }
  124.           res = x;
  125.         }
  126.       }
  127.     }
  128.     recalc();
  129.   }
  130.  
  131.   void recalc() { ch = getHash(); }
  132.   void rollLeft() { perform(12); }
  133.   void rollTop() { perform(13); }
  134.   void turnFront() { perform(14); }
  135.   void turn(int side, int k) { perform(2 * side + k); }
  136.  
  137.   hash getHash() {
  138.     hash res = 0;
  139.     for (int i = 0; i < 24; i++)
  140.       res = res * 29 + st[i];
  141.     return res;
  142.   }
  143.  
  144.   void print() {
  145.     eprintf("  %s%s\n", get(st[0]), get(st[1]));
  146.     eprintf("  %s%s\n", get(st[2]), get(st[3]));
  147.     for (int i = 1; i <= 4; i++)
  148.     for (int i2 = 0; i2 < 2; i2++)
  149.       eprintf("%s", get(st[i * 4 + i2]));
  150.     eprintf("\n");
  151.     for (int i = 1; i <= 4; i++)
  152.     for (int i2 = 2; i2 < 4; i2++)
  153.       eprintf("%s", get(st[i * 4 + i2]));
  154.     eprintf("\n");
  155.     eprintf("  %s%s\n", get(st[20]), get(st[21]));
  156.     eprintf("  %s%s\n", get(st[22]), get(st[23]));
  157.   }
  158.  
  159.   bool operator==(const Cube &c) const { return !memcmp(st, c.st, sizeof st); }
  160.   bool operator!=(const Cube &c) const { return  memcmp(st, c.st, sizeof st); }
  161.   bool operator<(const Cube &c) const {
  162.     if (ch != c.ch) return ch < c.ch;
  163.     return memcmp(st, c.st, sizeof st) < 0;
  164.   }
  165. };            
  166. char Cube::gbuf[16][5];
  167. const char* Cube::sufs = " +$-";
  168.  
  169. hash needh;
  170.  
  171. int ans;
  172. vector<pii> ops;
  173.  
  174. set<hash> was;
  175. clock_t end;
  176.  
  177. bool go(Cube c, int pr = -1, int dep = 0) {
  178.   hash h = c.getHash();
  179.   if (h == needh) return true;
  180.   if (dep >= ans) return false;
  181.  
  182.   if (was.count(h)) return false;
  183.   if (clock() >= end) return false;
  184.   was.insert(h);
  185.  
  186.   for (int i = 0; i < 6; i++) if (i != pr)
  187.   for (int i2 = 0; i2 < 2; i2++) {
  188.     Cube c2 = c;
  189.     c2.turn(i, i2);
  190.     if (go(c2, i, dep + 1)) {
  191.       ops.pb(mp(i, i2));
  192.       return true;
  193.     }
  194.   }
  195.   return false;
  196. }
  197.  
  198. vector<pii> restore(map<Cube, int> &fr, Cube c) {
  199.   vector<pii> res;
  200.   eprintf("restore\n");
  201.   c.print();
  202.   for (int step = 0;; step++) {
  203.     assert(fr.count(c));
  204.     const int cfr = fr[c];
  205.     if (cfr < 0) break;
  206.  
  207.     res.pb(mp(cfr >> 1, (cfr & 1)));
  208.     c.turn(cfr >> 1, !(cfr & 1)); c.recalc();
  209.   }
  210.   reverse(res.begin(), res.end());
  211.   return res;
  212. }
  213.  
  214. char f[6][100];
  215. int main() {
  216.   end = clock() + CLOCKS_PER_SEC * 1.8;
  217.   needh = Cube().getHash();
  218.  
  219.   freopen(TASKNAME ".in", "r", stdin);
  220.   freopen(TASKNAME ".out", "w", stdout);
  221.  
  222.   while (scanf("%s", f[0]) >= 1) {
  223.     for (int i = 1; i < 6; i++)
  224.       scanf("%s", f[i]);
  225.  
  226.     Cube c(f), c2;
  227.     map<Cube, int> fr, fr2;
  228.  
  229.     for (int step = 0; step < 2; step++) {
  230.       deque<pair<Cube, int> > q;
  231.       fr[c] = -1;
  232.       q.pb(mp(c, 0));
  233.  
  234.       while (!q.empty()) {
  235.         Cube c = q.front().first;
  236.         int d = q.front().second;
  237.         q.pop_front();
  238.  
  239.         if (fr2.count(c)) {
  240.           assert(step == 1);
  241.  
  242.           vector<pii> ops = restore(fr2, c), ops2 = restore(fr, c);
  243.           reverse(ops2.begin(), ops2.end());
  244.           for (int i = 0; i < sz(ops); i++)
  245.             printf("%c%c\n", "BLURDF"[ops[i].first], "+-"[ops[i].second]);
  246.           for (int i = 0; i < sz(ops2); i++)
  247.             printf("%c%c\n", "BLURDF"[ops2[i].first], "+-"[!ops2[i].second]);
  248.           goto end;
  249.         }
  250.  
  251.         if (d >= 6 || (step == 1 && d >= 5)) continue;
  252.         for (int i = 0; i < 6; i++)
  253.         for (int i2 = 0; i2 < 2; i2++) {
  254.           Cube c2 = c;
  255.           c2.turn(i, i2);
  256.           c2.recalc();
  257.           if (fr.count(c2)) continue;
  258.  
  259.           fr[c2] = i * 2 + i2;
  260.           q.pb(mp(c2, d + 1));
  261.         }
  262.       }
  263.  
  264.       swap(c, c2);
  265.       fr.swap(fr2);
  266.     }
  267.     printf("NO SOLUTION\n");
  268.     end:;
  269.   }
  270.   return 0;
  271. }
Add Comment
Please, Sign In to add comment