ccbeginner

UVa Q704

Feb 4th, 2020
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q704
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. string lr(string in){//s.size() := 24
  6.     string s = in;
  7.     char a = s[10], b = s[11];
  8.     for(int i = 11; i >= 2; --i)s[i] = s[i-2];
  9.     s[0] = a; s[1] = b;
  10.     for(int i = 21; i <= 23; ++i)s[i] = s[i-12];
  11.     return s;
  12. }
  13. string rr(string in){//s.size() := 24
  14.     string s = in;
  15.     char a = s[12], b = s[13];
  16.     for(int i = 12; i <= 21; ++i)s[i] = s[i+2];
  17.     s[22] = a; s[23] = b;
  18.     for(int i = 9; i <= 11; ++i)s[i] = s[i+12];
  19.     return s;
  20. }
  21. string ll(string in){//s.size() := 24
  22.     string s = in;
  23.     char a = s[0], b = s[1];
  24.     for(int i = 0; i <= 9; ++i)s[i] = s[i+2];
  25.     s[10] = a; s[11] = b;
  26.     for(int i = 21; i <= 23; ++i)s[i] = s[i-12];
  27.     return s;
  28. }
  29. string rl(string in){//s.size() := 24
  30.     string s = in;
  31.     char a = s[22], b = s[23];
  32.     for(int i = 23; i >= 14; --i)s[i] = s[i-2];
  33.     s[12] = a; s[13] = b;
  34.     for(int i = 9; i <= 11; ++i)s[i] = s[i+12];
  35.     return s;
  36. }
  37. string (*turn[])(string in) = {nullptr, lr, rr, ll, rl};
  38.  
  39. map<string, string> V, U;
  40. string ans;
  41.  
  42. void dfs1(int depth, string s, string vs){
  43.     V[s] = vs;
  44.     //cout << depth << ' ' << s << ' ' << vs << endl;
  45.     if(depth >= 8)return;
  46.     for(int i = 1; i <= 4; ++i){
  47.         string x = turn[i](s);
  48.         if(V.find(x) == V.end() || V[x].size() > vs.size()+1LL){
  49.             dfs1(depth+1, x, (char)((i+1)%4+'1') + vs);
  50.         }
  51.     }
  52. }
  53.  
  54. void dfs2(int depth, string s, string us){
  55.     U[s] = us;
  56.     if(V.find(s) != V.end() && ans.size() > us.size() + V[s].size())ans = us + V[s];
  57.     //cout << depth << ' ' << s << ' ' << us << endl;
  58.     if(depth >= 8)return;
  59.     for(int i = 1; i <= 4; ++i){
  60.         string x = turn[i](s);
  61.         if(U.find(x) == U.end() || U[x].size() > us.size()+1LL){
  62.             dfs2(depth+1, x, us + (char)(i+'0'));
  63.         }
  64.     }
  65. }
  66.  
  67. int main(){
  68.     int t,x;
  69.     string tar = "034305650121078709:90121";
  70.     dfs1(0, tar, "");
  71.     cin >> t;
  72.     while(t--){
  73.         U.clear();
  74.         ans = "000000000000000000000000";
  75.         string s;
  76.         for(int i = 0; i < 24; ++i){
  77.             cin >> x;
  78.             s += char(x+'0');
  79.         }
  80.         if(s == tar)cout << "PUZZLE ALREADY SOLVED\n";
  81.         else if(V.find(s) != V.end())cout << V[s] << endl;
  82.         else{
  83.             dfs2(0, s, "");
  84.             if(ans.size() <= 16)cout << ans << '\n';
  85.             else cout << "NO SOLUTION WAS FOUND IN 16 STEPS\n";
  86.         }
  87.     }
  88.     return 0;
  89. }
RAW Paste Data