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
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
| #include <algorithm>
#include <memory.h>
#include <queue>
#include <iostream>
using namespace std;
int map[11][11];
int v[11][11][3], n, sx, sy, ans;
int kx[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int ky[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
int bx[4] = {-1, 1, 1, -1};
int by[4] = {-1, -1, 1, 1};
int lx[4] = {0, 1, 0, -1};
int ly[4] = {-1, 0, 1, 0};
queue<pair<int, int>> q;
struct st {
int y, x, p, item;
};
void setMin(pair<int, int> p) {
for(int i = 0; i < 3; ++i)
if(v[p.first][p.second][i] == -1)
v[p.first][p.second][i] = 987654321;
int n1 = v[p.first][p.second][0], n2 =v[p.first][p.second][1], n3=v[p.first][p.second][2];
v[p.first][p.second][0] = min(n1, min(n2,n3)+1);
v[p.first][p.second][1] = min(n2, min(n1,n3)+1);
v[p.first][p.second][2] = min(n3, min(n1,n2)+1);
ans = min(n1, min(n2,n3));
}
void bfs() {
q.push(make_pair(sy, sx));
v[sy][sx][0] = v[sy][sx][1] = v[sy][sx][2] = 0;
while(map[q.front().first][q.front().second] != n*n) {
pair<int,int> p = q.front();
q.pop();
queue<st> stq;
stq.push(st{.y = p.first, .x = p.second, .p = v[p.first][p.second][0], .item = 0});
stq.push(st{.y = p.first, .x = p.second, .p = v[p.first][p.second][1], .item = 1});
stq.push(st{.y = p.first, .x = p.second, .p = v[p.first][p.second][2], .item = 2});
int visit[10][10][3];
memset(visit,-1,sizeof(visit));
while(!stq.empty()) {
st s = stq.front();
stq.pop();
switch (s.item) {
case 0: {
for(int i = 0; i < 8; ++i) {
int ny = s.y + ky[i];
int nx = s.x + kx[i];
if(0 <= ny && ny < n && 0 <= nx && nx < n) {
if(visit[ny][nx][0] == -1 || visit[ny][nx][0] > s.p + 1) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 1, .item = 0});
visit[ny][nx][0] = s.p + 1;
}
if(visit[ny][nx][1] == -1 || visit[ny][nx][1] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 1});
visit[ny][nx][1] = s.p + 2;
}
if(visit[ny][nx][2] == -1 || visit[ny][nx][2] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 2});
visit[ny][nx][2] = s.p + 2;
}
if(map[ny][nx] == map[p.first][p.second] + 1) {
if(q.empty())
q.push(make_pair(ny,nx));
if(v[ny][nx][0] == -1 || v[ny][nx][0] > s.p + 1)
v[ny][nx][0] = s.p + 1;
}
}
}
}
break;
case 1: {
for(int i = 0; i < 4; ++i) {
for(int j = 1; j <= 10; ++j) {
int ny = s.y + by[i] * j;
int nx = s.x + bx[i] * j;
if (0 <= ny && ny < n && 0 <= nx && nx < n) {
if(visit[ny][nx][1] == -1 || visit[ny][nx][1] > s.p + 1) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 1, .item = 1});
visit[ny][nx][1] = s.p + 1;
}
if(visit[ny][nx][0] == -1 || visit[ny][nx][0] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 0});
visit[ny][nx][0] = s.p + 2;
}
if(visit[ny][nx][2] == -1 || visit[ny][nx][2] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 2});
visit[ny][nx][2] = s.p + 2;
}
if(map[ny][nx] == map[p.first][p.second] + 1) {
if(q.empty())
q.push(make_pair(ny,nx));
if(v[ny][nx][1] == -1 || v[ny][nx][1] > s.p + 1)
v[ny][nx][1] = s.p + 1;
}
}
}
}
}
break;
case 2: {
for(int i = 0; i < 4; ++i) {
for(int j = 1; j<= 10; ++j) {
int ny = s.y + ly[i] * j;
int nx = s.x + lx[i] * j;
if (0 <= ny && ny < n && 0 <= nx && nx < n) {
if(visit[ny][nx][2] == -1 || visit[ny][nx][2] > s.p + 1) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 1, .item = 2});
visit[ny][nx][2] = s.p + 1;
}
if(visit[ny][nx][0] == -1 || visit[ny][nx][0] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 0});
visit[ny][nx][0] = s.p + 2;
}
if(visit[ny][nx][1] == -1 || visit[ny][nx][1] > s.p + 2) {
stq.push(st{.y = ny, .x = nx, .p = s.p + 2, .item = 1});
visit[ny][nx][1] = s.p + 2;
}
if(map[ny][nx] == map[p.first][p.second] + 1) {
if(q.empty())
q.push(make_pair(ny,nx));
if(v[ny][nx][2] == -1 || v[ny][nx][2] > s.p + 1)
v[ny][nx][2] = s.p + 1;
}
}
}
}
}
break;
}
}
setMin(q.front());
}
}
int main(void) {
scanf("%d",&n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) {
scanf("%d", &map[i][j]);
if(map[i][j] == 1) {
sx = j;
sy = i;
}
}
memset(v, -1, sizeof(v));
bfs();
printf("%d",ans);
}
|
