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
|
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
typedef long long LL;
const int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int inf = 0x3f3f3f3f;
const int maxr = 27;
const int maxc = 31;
char s[10];
int d[maxr][maxc][maxr][maxc];
int cnt, kx[maxr * maxc], ky[maxr * maxc];
struct node {
int x, y;
node() {}
node(int x, int y) : x(x), y(y) {}
};
queue<node> q;
int Dis(int x, int y) {
return max(abs(x), abs(y));
}
int Sum(int x, int y) {
int sum = 0;
for (int i = 1; i < cnt; ++i) {
sum += d[kx[i]][ky[i]][x][y];
if (sum > inf) {
sum = inf;
}
}
return sum;
}
int main() {
freopen("camelot.in", "r", stdin);
freopen("camelot.out", "w", stdout);
int r, c;
scanf("%d%d%s%d", &c, &r, s, &ky[0]);
kx[cnt++] = s[0] - 'A', --ky[0];
while (~scanf("%s%d", s, &ky[cnt])) {
kx[cnt] = s[0] - 'A', --ky[cnt];
++cnt;
}
memset(d, 0x3f, sizeof d);
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
while (!q.empty()) {
q.pop();
}
d[i][j][i][j] = 0;
q.push(node(i, j));
while (!q.empty()) {
node k = q.front();
q.pop();
for (int l = 0; l < 8; ++l) {
int a = k.x + dx[l], b = k.y + dy[l];
if (a >= 0 && a < r && b >= 0 && b < c && d[i][j][a][b] == inf) {
d[i][j][a][b] = d[i][j][k.x][k.y] + 1;
q.push(node(a, b));
}
}
}
}
}
int ans = inf;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
int len = Sum(i, j);
if (len < ans) {
int tmp = len + Dis(kx[0] - i, ky[0] - j);
for (int k = 1; k < cnt; ++k) {
for (int l = -2; l <= 2; ++l) {
for (int m = -2; m <= 2; ++m) {
int px = kx[0] + l, py = ky[0] + m;
if (px >= 0 && px < r && py >= 0 && py < c) {
tmp = min(tmp, len - d[kx[k]][ky[k]][i][j] + Dis(l, m) + d[kx[k]][ky[k]][px][py] + d[px][py][i][j]);
}
}
}
}
ans = min(ans, tmp);
}
}
}
printf("%d\n", ans);
return 0;
}
|