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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<vector>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring>
#include<functional>
#include<map>
#include<cmath>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> PII;
const int maxn = 1e6+5;
int goal[10][2];
int G[10][10];
int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
char dir[] = {‘d’,‘l’,‘r’,‘u’};
int manhattan()
{
int sum = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
int w = G[i][j];
if(w==0)continue;
sum += abs(goal[w][0] - i) + abs(goal[w][1] - j);
}
}
return sum;
}
char sta[500];
bool flag = 0;
void idastar(int x,int y,int pre,int step,int top)
{
if(flag)return;
for(int i=0;i<4;i++){
if(flag)return;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 2||ny>2||nx < 0||ny<0)continue;
if(pre + i == 3)continue;
swap(G[x][y],G[nx][ny]);
int mht = manhattan();
if(mht==0){
cout << step+1 << endl;
sta[step] = dir[i];
cout << sta << endl;
flag = 1;
return;
}
if(mht + step <= top){
if(flag) return;
sta[step] = dir[i];
idastar(nx,ny,i,step+1,top);
}
swap(G[x][y],G[nx][ny]);
}
}
int main(int argc, char const *argv[])
{
int T = 0;
cin >> T;
int Case = 1;
while(T–){
memset(sta,0,sizeof(sta));
string s1,s2;
cin >> s1 >> s2;
cout << “Case “ << Case++ << “: “;
if(s1==s2){
cout << “0” << endl;
cout <<endl;
continue;
}
flag = 0;
int bx,by;
for(int i=0;i<s1.length();i++){
if(s1[i]==‘X’){
G[i/3][i%3] = 0;
bx = i/3;
by = i%3;
}else{
G[i/3][i%3] = s1[i]-‘0’;
}
}
for(int i=0;i<s2.length();i++){
int w = 0;
if(s2[i]==‘X’){
w = 0;
}else{
w = s2[i]-‘0’;
}
goal[w][0] = i/3;
goal[w][1] = i%3;
}
int top = 0;
while(++top){
idastar(bx,by,-1,0,top);
if(flag)
break;
}
}
return 0;
}
|
