贴出代码，先鸽了，学会了A*再来更
I1
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161/*
@description: hdu-1043
@author: universal42@163.com
@solution: bfs 康拓展开 c++能过
*/
using namespace std;
const int maxn=362881;
int fac[]={1,1,2,6,24,120,720,5040,40320};//记录阶乘
bool vis[maxn];
char dir[]={'d','u','r','l'};
const string err="unsolvable";
int dx[]={-1,1,0,0};//上下左右
int dy[]={0,0,-1,1};
char x;
char T_state[9];
int T_cantor;
int T_zero;
char RA[9];
int RA_zero;
string path[maxn];
struct node{
int zero;//记录0/x的位置
string path;//记录路径
int cantor;//康拓编码
node(){};
node(int _zero,string _path,int _cantor):zero(_zero),path(_path),cantor(_cantor){};
}st;
queue<node> q;
int Cantor(char *s){//对给定的状态求康拓展开编码
int ct=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;j++) if(s[i]>s[j]) cnt++;
ct+=(cnt*fac[9-i-1]);
}
return ct;
}
void CantorReverse(int x,char *s){//给定康拓编码，返回状态数组
int vst[20]={0};
for(int i=0;i<9;i++){
int t=x/fac[9-i-1];
int j;
for(j=0;j<9;j++){
if(!vst[j]){
if(t==0) break;
t--;
}
}
s[i]='0'+j;
vst[j]=1;
x%=fac[9-i-1];
}
}
void init(){
for(int i=0;i<8;i++) T_state[i]=i+1+'0';
T_state[8]='0';
T_zero=8;//记录初始状态0的位置
T_cantor=Cantor(T_state);
}
void Swap(char &a,char &b){
char t=a;
a=b;
b=t;
}
void bfs(){
mset(vis,false);
st.cantor=T_cantor,st.zero=T_zero,st.zero=T_zero,vis[st.cantor]=1;
q.push(st);
node f;
char tmp[9];
char na[9];//获取当前Cantor值的对应数组
while(!q.empty()){
f=q.front();
q.pop();
CantorReverse(f.cantor,na);//获取当前结点对应的状态数组
int fx=f.zero/3,fy=f.zero%3;
if(fx>=1){//0可以上移
Swap(na[fx*3+fy],na[(fx-1)*3+fy]);
int val=Cantor(na);
if(!vis[val]){
vis[val]=1;
q.push(node((fx-1)*3+fy,f.path+'d',val));
path[val]=f.path+'d';
}
Swap(na[fx*3+fy],na[(fx-1)*3+fy]);
}
if(fx<=1){//可以下移
Swap(na[fx*3+fy],na[(fx+1)*3+fy]);
int val=Cantor(na);
if(!vis[val]){
vis[val]=1;
q.push(node((fx+1)*3+fy,f.path+'u',val));//下面的数上移
path[val]=f.path+'u';
}
Swap(na[fx*3+fy],na[(fx+1)*3+fy]);
}
if(fy>=1){//可以左移
Swap(na[fx*3+fy],na[fx*3+fy-1]);
int val=Cantor(na);
if(!vis[val]){
vis[val]=1;
q.push(node(fx*3+fy-1,f.path+'r',val));//左边的数右移
path[val]=f.path+'r';
}
Swap(na[fx*3+fy],na[fx*3+fy-1]);
}
if(fy<=1){//可以左移
Swap(na[fx*3+fy],na[fx*3+fy+1]);
int val=Cantor(na);
if(!vis[val]){
vis[val]=1;
q.push(node(fx*3+fy+1,f.path+'l',val));//右边的数左移
path[val]=f.path+'l';
}
Swap(na[fx*3+fy],na[fx*3+fy+1]);
}
}
}
int main() {
//cls;
freopen("in.in","r",stdin);
init();
bfs();
while(cin>>x){
if(x=='x'){
RA[0]='0';
RA_zero=0;
}
else RA[0]=x;
for(int i=1;i<=8;i++){
cin>>x;
if(x=='x'){
RA[i]='0';
RA_zero=i;
}
else RA[i]=x;
}
int val=Cantor(RA);
if(vis[val]){
for(int i=path[val].length()-1;i>=0;i--) cout<<path[val][i];
cout<<endl;
}
else cout<<err<<endl;
}
return 0;
}