Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- set<string> used;
- struct sq{
- long long n;
- string path,id;
- };
- queue<sq> q;
- void l1(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"L1";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[0];s2=b.id[1];s3=b.id[2];
- b.id[0]=s2;b.id[1]=s3;b.id[2]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void r1(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"R1";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[0];s2=b.id[1];s3=b.id[2];
- b.id[0]=s3;b.id[1]=s1;b.id[2]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void l2(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"L2";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[3];s2=b.id[4];s3=b.id[5];
- b.id[3]=s2;b.id[4]=s3;b.id[5]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void r2(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"R2";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[3];s2=b.id[4];s3=b.id[5];
- b.id[3]=s3;b.id[4]=s1;b.id[5]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void l3(sq a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"L3";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[6];s2=b.id[7];s3=b.id[8];
- b.id[6]=s2;b.id[7]=s3;b.id[8]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void r3(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"R3";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[6];s2=b.id[7];s3=b.id[8];
- b.id[6]=3;b.id[7]=s1;b.id[8]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void d1(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"D1";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[0];s2=b.id[3];s3=b.id[6];
- b.id[0]=s3;b.id[3]=s1;b.id[6]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void u1(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"U1";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[0];s2=b.id[3];s3=b.id[6];
- b.id[0]=s2;b.id[3]=s3;b.id[6]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void d2(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"D2";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[1];s2=b.id[4];s3=b.id[7];
- b.id[1]=s3;b.id[4]=s1;b.id[7]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void u2(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"U2";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[1];s2=b.id[4];s3=b.id[7];
- b.id[1]=s2;b.id[4]=s3;b.id[7]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void d3(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"D3";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[2];s2=b.id[5];s3=b.id[8];
- b.id[2]=s3;b.id[5]=s1;b.id[8]=s2;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- void u3(sq &a){
- sq b;
- b.n=a.n+1;
- b.path=a.path+"U3";
- b.id=a.id;
- char s1,s2,s3;
- s1=b.id[2];s2=b.id[5];s3=b.id[8];
- b.id[2]=s2;b.id[5]=s3;b.id[8]=s1;
- if(used.count(b.id)!=1){q.push(b);used.insert(b.id);}
- }
- int main() {
- int t;
- string id;
- for(int i=0;i<9;i++){
- cin>>t;
- id+=(t+48);
- }
- sq fst;
- fst.n=0;
- fst.path="";
- fst.id=id;
- string s[8];
- s[0]="276951438";
- s[1]="492357816";
- s[2]="834159672";
- s[3]="618753294";
- s[4]="438951276";
- s[5]="672159834";
- s[6]="294753618";
- s[7]="816357492";
- used.insert(fst.id);
- q.push(fst);
- long long m=0;
- string str;
- bool goaway=false;
- while(!q.empty()){
- for(int i=0;i<8;i++){
- if(q.front().id==s[i]){
- m=q.front().n;
- str=q.front().path;
- goaway=true;
- break;
- }
- }
- if(goaway)break;
- 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);
- q.pop();
- }
- if(m==0){cout<<0<<endl;return 0;}
- cout<<m<<endl;
- for(int i=0;i<str.size();i+=2){
- cout<<str[i]<<str[i+1]<<((i!=str.size()-2)?"\n":"");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement