[HNOI 2006] 马步距离

题目大意

给定起点坐标 (xp,  yp)(x_p, \; y_p) 和终点坐标 (xs,  ys)(x_s, \; y_s) ,求至少经过多少次马步移动。

x,  y10,000,000|x|, \; |y| \leqslant 10,000,000

题目链接

【HNOI 2006】马步距离 - Luogu 2060

题解

大数据贪心,小数据暴力。。。

贪心为:用 (+2,+1)(+2,+1)(+2, +1) \rightarrow (+2, +1)(+2,+1)(+2,1)(+2, +1) \rightarrow (+2, -1) 两种移动(中间可以调换 xx 坐标与 yy 坐标,这里把 xx 坐标始终调换为大的那个)把距离缩减到暴力范围内。

代码

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
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
const int FORCE_LIMIT = 50;
struct Point {
int x, y, dist;
bool vis;
} P[FORCE_LIMIT * 2 + 1][FORCE_LIMIT * 2 + 1];
bool valid(int x, int y) {
return (x >= 0) && (y >= 0) && (x <= FORCE_LIMIT << 1) && (y <= FORCE_LIMIT << 1);
}
int bfs(int x, int y) {
for (int i = 0; i <= FORCE_LIMIT << 1; i++) for (int j = 0; j <= FORCE_LIMIT << 1; j++) {
P[i][j].x = i;
P[i][j].y = j;
P[i][j].vis = false;
}
static int d[8][2] = {
{-1, 2}, {1, 2},
{-1, -2}, {1, -2},
{2, -1}, {2, 1},
{-2, -1}, {-2, 1}
};
std::queue<Point *> q;
q.push(&P[x][y]);
P[x][y].dist = 0;
while (!q.empty()) {
Point *u = q.front();
q.pop();
if (u->vis) continue;
u->vis = true;
for (int i = 0; i < 8; i++) {
int vx = u->x + d[i][0], vy = u->y + d[i][1];
if (valid(vx, vy)) {
P[vx][vy].dist = u->dist + 1;
if (vx == FORCE_LIMIT && vy == FORCE_LIMIT) return P[vx][vy].dist;
q.push(&P[vx][vy]);
}
}
}
return -1;
}
int main() {
int sx, sy, tx, ty;
scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
int dx = abs(tx - sx), dy = abs(ty - sy);
int ans = 0;
while (dx + dy >= FORCE_LIMIT) {
if (dx < dy) std::swap(dx, dy);
if (dx - 4 >= dy * 2) dx -= 4;
else dx -= 4, dy -= 2;
ans += 2;
}
dx += FORCE_LIMIT, dy += FORCE_LIMIT;
printf("%d\n", bfs(dx, dy) + ans);
return 0;
}