Posted on 2009-06-04 13:50
superman 阅读(219)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 struct point {
7 int x, y;
8 point operator+(const point &p) const {
9 point np = { x + p.x, y + p.y };
10 return np;
11 }
12 } ;
13
14 int r, c, knightsNum;
15 point king, knights[30 * 26];
16
17 const point kinghtDir[8] = {
18 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
19 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
20 } ;
21
22 inline bool inside(const point &p) {
23 return p.x >= 0 && p.x < r && p.y >= 0 && p.y < c;
24 }
25
26 int dist[30][26][30][26];
27 void spfa(const point &s)
28 {
29 for (int i = 0; i < r; i++)
30 for (int j = 0; j < c; j++)
31 dist[s.x][s.y][i][j] = INT_MAX;
32 dist[s.x][s.y][s.x][s.y] = 0;
33
34 queue<point> q;
35 q.push(s);
36
37 point cp; //current point
38 point np; //next point
39 while (q.empty() == false)
40 {
41 cp = q.front(); q.pop();
42 for (int i = 0; i < 8; i++)
43 {
44 np = cp + kinghtDir[i];
45 if (inside(np) && dist[s.x][s.y][cp.x][cp.y] + 1 < dist[s.x][s.y][np.x][np.y])
46 {
47 dist[s.x][s.y][np.x][np.y] = dist[s.x][s.y][cp.x][cp.y] + 1;
48 q.push(np);
49 }
50 }
51 }
52 }
53
54 int ans = INT_MAX;
55 void gather(int tx, int ty)
56 {
57 int sum = 0;
58 for (int i = 0; i < knightsNum; i++)
59 sum += dist[knights[i].x][knights[i].y][tx][ty];
60
61 if (sum > ans)
62 return;
63
64 for (int i = max(0, king.x - 2); i <= min(r - 1, king.x + 2); i++)
65 for (int j = max(0, king.y - 2); j <= min(c - 1, king.y + 2); j++)
66 {
67 int tmp;
68 if (i == king.x && j == king.y)
69 tmp = 0;
70 else
71 {
72 if (abs(i - king.x) == 1 || abs(j - king.y == 1))
73 tmp = 1;
74 else
75 tmp = 2;
76 }
77 for (int k = 0; k < knightsNum; k++)
78 if (dist[knights[k].x][knights[k].y][i][j] != INT_MAX &&
79 dist[i][j][tx][ty] != INT_MAX)
80 ans <?= (sum - dist[knights[k].x][knights[k].y][tx][ty]
81 + tmp + dist[knights[k].x][knights[k].y][i][j] + dist[i][j][tx][ty]);
82 }
83 }
84
85 int main()
86 {
87 freopen("camelot.in", "r", stdin);
88 freopen("camelot.out", "w", stdout);
89
90 cin >> r >> c;
91
92 {
93 char a; int b;
94 cin >> a >> b;
95 king.y = a - 'A', king.x = b - 1;
96 while (cin >> a >> b)
97 {
98 knights[knightsNum].y = a - 'A';
99 knights[knightsNum].x = b - 1;
100 knightsNum++;
101 }
102 }
103
104 if (knightsNum == 0)
105 {
106 cout << 0 << endl;
107 return 0;
108 }
109
110 for (int i = 0; i < r; i++)
111 for (int j = 0; j < c; j++)
112 {
113 point cp = { i, j };
114 spfa(cp);
115 }
116
117 for (int i = 0; i < r; i++)
118 for (int j = 0; j < c; j++)
119 gather(i, j);
120
121 cout << ans << endl;
122
123 return 0;
124 }
125