Advertisement
Guest User

Untitled

a guest
May 25th, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. set<string> used;
  4. struct sq{
  5.     long long n;
  6.     string path,id;
  7. };
  8. queue<sq> q;
  9.  
  10. void l1(sq &a){
  11.     sq b;
  12.     b.n=a.n+1;
  13.     b.path=a.path+"L1";
  14.     b.id=a.id;
  15.     char s1,s2,s3;
  16.     s1=b.id[0];s2=b.id[1];s3=b.id[2];
  17.     b.id[0]=s2;b.id[1]=s3;b.id[2]=s1;
  18.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  19. }
  20. void r1(sq &a){
  21.     sq b;
  22.     b.n=a.n+1;
  23.     b.path=a.path+"R1";
  24.     b.id=a.id;
  25.     char s1,s2,s3;
  26.     s1=b.id[0];s2=b.id[1];s3=b.id[2];
  27.     b.id[0]=s3;b.id[1]=s1;b.id[2]=s2;
  28.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  29. }
  30.  
  31. void l2(sq &a){
  32.     sq b;
  33.     b.n=a.n+1;
  34.     b.path=a.path+"L2";
  35.     b.id=a.id;
  36.     char s1,s2,s3;
  37.     s1=b.id[3];s2=b.id[4];s3=b.id[5];
  38.     b.id[3]=s2;b.id[4]=s3;b.id[5]=s1;
  39.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  40. }
  41. void r2(sq &a){
  42.     sq b;
  43.     b.n=a.n+1;
  44.     b.path=a.path+"R2";
  45.     b.id=a.id;
  46.     char s1,s2,s3;
  47.     s1=b.id[3];s2=b.id[4];s3=b.id[5];
  48.     b.id[3]=s3;b.id[4]=s1;b.id[5]=s2;
  49.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  50. }
  51.  
  52. void l3(sq a){
  53.     sq b;
  54.     b.n=a.n+1;
  55.     b.path=a.path+"L3";
  56.     b.id=a.id;
  57.     char s1,s2,s3;
  58.     s1=b.id[6];s2=b.id[7];s3=b.id[8];
  59.     b.id[6]=s2;b.id[7]=s3;b.id[8]=s1;
  60.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  61. }
  62. void r3(sq &a){
  63.     sq b;
  64.     b.n=a.n+1;
  65.     b.path=a.path+"R3";
  66.     b.id=a.id;
  67.     char s1,s2,s3;
  68.     s1=b.id[6];s2=b.id[7];s3=b.id[8];
  69.     b.id[6]=3;b.id[7]=s1;b.id[8]=s2;
  70.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  71. }
  72.  
  73. void d1(sq &a){
  74.     sq b;
  75.     b.n=a.n+1;
  76.     b.path=a.path+"D1";
  77.     b.id=a.id;
  78.     char s1,s2,s3;
  79.     s1=b.id[0];s2=b.id[3];s3=b.id[6];
  80.     b.id[0]=s3;b.id[3]=s1;b.id[6]=s2;
  81.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  82. }
  83. void u1(sq &a){
  84.     sq b;
  85.     b.n=a.n+1;
  86.     b.path=a.path+"U1";
  87.     b.id=a.id;
  88.     char s1,s2,s3;
  89.     s1=b.id[0];s2=b.id[3];s3=b.id[6];
  90.     b.id[0]=s2;b.id[3]=s3;b.id[6]=s1;
  91.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  92. }
  93.  
  94. void d2(sq &a){
  95.     sq b;
  96.     b.n=a.n+1;
  97.     b.path=a.path+"D2";
  98.     b.id=a.id;
  99.     char s1,s2,s3;
  100.     s1=b.id[1];s2=b.id[4];s3=b.id[7];
  101.     b.id[1]=s3;b.id[4]=s1;b.id[7]=s2;
  102.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  103. }
  104. void u2(sq &a){
  105.     sq b;
  106.     b.n=a.n+1;
  107.     b.path=a.path+"U2";
  108.     b.id=a.id;
  109.     char s1,s2,s3;
  110.     s1=b.id[1];s2=b.id[4];s3=b.id[7];
  111.     b.id[1]=s2;b.id[4]=s3;b.id[7]=s1;
  112.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  113. }
  114.  
  115. void d3(sq &a){
  116.     sq b;
  117.     b.n=a.n+1;
  118.     b.path=a.path+"D3";
  119.     b.id=a.id;
  120.     char s1,s2,s3;
  121.     s1=b.id[2];s2=b.id[5];s3=b.id[8];
  122.     b.id[2]=s3;b.id[5]=s1;b.id[8]=s2;
  123.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  124. }
  125. void u3(sq &a){
  126.     sq b;
  127.     b.n=a.n+1;
  128.     b.path=a.path+"U3";
  129.     b.id=a.id;
  130.     char s1,s2,s3;
  131.     s1=b.id[2];s2=b.id[5];s3=b.id[8];
  132.     b.id[2]=s2;b.id[5]=s3;b.id[8]=s1;
  133.     if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
  134. }
  135.  
  136. int main() {
  137.     int t;
  138.     string id;
  139.     for(int i=0;i<9;i++){
  140.         cin>>t;
  141.         id+=(t+48);
  142.     }
  143.     sq fst;
  144.     fst.n=0;
  145.     fst.path="";
  146.     fst.id=id;
  147.     string s[8];
  148.     s[0]="276951438";
  149.     s[1]="492357816";
  150.     s[2]="834159672";
  151.     s[3]="618753294";
  152.     s[4]="438951276";
  153.     s[5]="672159834";
  154.     s[6]="294753618";
  155.     s[7]="816357492";
  156.     used.insert(fst.id);
  157.     q.push(fst);
  158.     long long m=0;
  159.     string str;
  160.     bool goaway=false;
  161.     while(!q.empty()){
  162.         for(int i=0;i<8;i++){
  163.         if(q.front().id==s[i]){
  164.             m=q.front().n;
  165.             str=q.front().path;
  166.             goaway=true;
  167.             break;
  168.             }
  169.         }
  170.         if(goaway)break;
  171.         sq temp=q.front();l1(temp);l2(temp);l3(temp);r1(temp);r2(temp);r3(temp);d1(temp);d2(temp);d3(temp);u1(temp);u2(temp);u3(temp);
  172.         q.pop();
  173.     }
  174.     if(m==0){cout<<0<<endl;return 0;}
  175.     cout<<m<<endl;
  176.     for(int i=0;i<str.size();i+=2){
  177.         cout<<str[i]<<str[i+1]<<((i!=str.size()-2)?"\n":"");
  178.     }
  179.     return 0;
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement