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
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[50];
int mp[5][5];
int sx, sy;
int ans[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
int k = 2;
bool check() {
for(int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if(ans[i][j] != mp[i][j]) return 0;;
}
}
return 1;
}
bool test(int step) {
int diff = 0;
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= 3; j++) {
if(ans[i][j] != mp[i][j]) {
diff++;
}
if(diff + step > k) {
return 0;
}
}
}
return 1;
}
int judge;
void Astar(int step, int x, int y, int pre) {
if(step == k) {
if(check()) judge = 1;
return;
}
if(judge) return;
for(int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(xx < 1 || xx > 3 || y < 1 || y > 3 || pre+i == 3) continue;
swap(mp[xx][yy], mp[x][y]);
if(test(step)) Astar(step+1, xx, yy, i);
swap(mp[xx][yy], mp[x][y]);
}
}
int main() {
scanf("%s", s);
for(int i = 0 ; i < 9; i++) {
mp[i/3+1][i%3+1] = s[i] - '0';
if(s[i] - '0' == 0) {
sx = i/3 + 1;
sy = i%3 + 1;
}
}
if(check()) {
printf("0\n");
return 0;
}
while(++k) {
Astar(0, sx, sy, -1);
if(judge) {
printf("%d\n", k);
break;
}
}
return 0;
}
|
