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
| #include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int tb[4][4];
int x, y;
int iabs(int a){
return max(a, -a);
}
int func(){
int step_cnt = 0;
for(int lx = 0;lx < 4;lx++)
for(int ly = 0;ly < 4;ly++){
if(tb[lx][ly] == 16) continue;
int v = tb[lx][ly]-1;
step_cnt += iabs(v%4 - ly) + iabs(v/4 - lx);
}
return step_cnt;
}
bool dfs(int h, int mh, int pre_d){
if(h == mh){
for(int lx = 0;lx < 4;lx++)
for(int ly = 0;ly < 4;ly++)
if(lx*4 + ly != tb[lx][ly]-1)
return false;
return true;
}
if(func() + h > mh)
return false;
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
for(int d = 0;d < 4;d++){
if(pre_d + d == 3) continue;
int tx = x, ty = y;
int nx = x + dx[d], ny = y + dy[d];
if(nx < 0 or nx > 3 or ny < 0 or ny > 3)
continue;
swap(tb[x][y], tb[nx][ny]);
x = nx, y = ny;
if(dfs(h+1, mh, d)) return true;
x = tx, y = ty;
swap(tb[x][y], tb[nx][ny]);
}
return false;
}
int main(){
for(int lx = 0;lx < 4;lx++)
for(int ly = 0;ly < 4;ly++){
scanf("%d", &tb[lx][ly]);
if(tb[lx][ly] == 0){
tb[lx][ly] = 16;
x = lx, y = ly;
}
}
int inv_cnt = 0;
for(int lx = 0;lx < 16;lx++)
for(int ly = lx+1;ly < 16;ly++){
int a = tb[lx%4][lx/4], b = tb[ly%4][ly/4];
if(a == 16 or b == 16) continue;
inv_cnt += a > b;
}
if(inv_cnt%2 == y%2){
puts("-1");
return 0;
}
int s = func(); while(!dfs(0, s, -1)) s++;
printf("%d\n", s);
return 0;
}
|