1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
char tmp;
string final="123456789",res;
map<string,pair<string,string>> ans;
string input;
string fix(string s,int line, int type){
if(type==0){
int px=line*3;
char a=s[px],b=s[px+1],c=s[px+2];
s[px]=b;
s[px+1]=c;
s[px+2]=a;
return s;
}
else{
int px=line;
char a=s[px],b=s[px+3],c=s[px+6];
s[px]=c;
s[px+3]=a;
s[px+6]=b;
return s;
}
}
string fix_to_str(int line, int type){
string ret;
if(type==0) ret="H";
else ret="V";
ret+=(char)('0'+line);
return ret;
}
int main(){
IOS
queue<string>q;
map<string,bool> inq;
q.emplace(final);
inq[final]=true;
ans[final]=make_pair("end","end");
while(!q.empty()){
string now=q.front();
q.pop();
for(int i=0 ; i<3 ; i++){
res=fix(now,i,0);
if(!inq.count(res)){
ans[res]=make_pair(fix_to_str(i+1,0),now);
q.emplace(res);
inq[res]=true;
}
res=fix(now,i,1);
if(!inq.count(res)){
ans[res]=make_pair(fix_to_str(i+1,1),now);
q.emplace(res);
inq[res]=true;
}
}
}
while(cin>>input && input!="0"){
for(int i=0 ; i<3 ; i++){
for(int j=0 ; j<3 ; j++){
if(i==0 && j==0) continue;
cin>>tmp;
input+=tmp;
}
}
if(ans.count(input)){
if(input==final){
cout<<"0\n";
}
else{
string nxt=input;
int cnt=0;
string out;
while(ans[nxt].second!="end"){
out+=ans[nxt].first;
nxt=ans[nxt].second;
cnt++;
}
cout<<cnt<<" "<<out<<"\n";
}
}
else{
cout<<"Not solvable\n";
}
}
return 0;
}
|