A. Lame King
You are given a checkerboard of size $201 \times 201$, i. e. it has $201$ rows and $201$ columns. The rows of this checkerboard are numbered from $-100$ to $100$ from bottom to top. The columns of this checkerboard are numbered from $-100$ to $100$ from left to right. The notation $(r, c)$ denotes the cell located in the $r$-th row and the $c$-th column.
There is a king piece at position $(0, 0)$ and it wants to get to position $(a, b)$ as soon as possible. In this problem our king is lame. Each second, the king makes exactly one of the following five moves.
- Skip move. King's position remains unchanged.
- Go up. If the current position of the king is $(r, c)$ he goes to position $(r + 1, c)$.
- Go down. Position changes from $(r, c)$ to $(r - 1, c)$.
- Go right. Position changes from $(r, c)$ to $(r, c + 1)$.
- Go left. Position changes from $(r, c)$ to $(r, c - 1)$.
King is not allowed to make moves that put him outside of the board. The important consequence of the king being lame is that he is not allowed to make the same move during two consecutive seconds. For example, if the king goes right, the next second he can only skip, go up, down, or left.
What is the minimum number of seconds the lame king needs to reach position $(a, b)$?
Input
The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follow $t$ lines containing one test case description each.
Each test case consists of two integers $a$ and $b$ ($-100 \leq a, b \leq 100$) — the position of the cell that the king wants to reach. It is guaranteed that either $a \ne 0$ or $b \ne 0$.
Output
Print $t$ integers. The $i$-th of these integers should be equal to the minimum number of seconds the lame king needs to get to the position he wants to reach in the $i$-th test case. The king always starts at position $(0, 0)$.
Example
input
5 -4 1 4 4 0 -6 -5 -4 7 -8
output
7 8 11 9 15
Note
One of the possible solutions for the first example is: go down, go right, go down, go right, go down, go left, go down.
One of the possible solutions for the second example is to alternate "go right" and "go up" moves $4$ times each.
One of the possible solutions for the third example is to alternate "go left" and "skip" moves starting with "go left". Thus, "go left" will be used $6$ times, and "skip" will be used $5$ times.
解题思路
好似，比赛的时候想了半天都不会做，真就nm是个傻逼。搞到心态炸了这场掉大分。
是真不会做，最后硬是写了个bfs求最短路，然后查表输出答案，时间复杂度为$O(n^2)$，这种做法就不讲了。
#include <bits/stdc++.h>
using namespace std;
const int N = 210, B = 100;
struct Node {
int x, y, d;
}q[N * N * 5];
int dist[N][N][5], ans[N][N];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
int main() {
int hh = 0, tt = -1;
memset(dist, 0x3f, sizeof(dist));
memset(ans, 0x3f, sizeof(ans));
for (int i = 0; i < 5; i++) {
q[++tt] = {B, B, i};
dist[B][B][i] = 0;
}
while (hh <= tt) {
Node t = q[hh++];
for (int i = 0; i < 5; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 0 || x > 200 || y < 0 || y > 200) continue;
if (t.d == i) continue;
if (dist[x][y][i] > dist[t.x][t.y][t.d] + 1) {
dist[x][y][i] = dist[t.x][t.y][t.d] + 1;
ans[x][y] = min(ans[x][y], dist[x][y][i]);
q[++tt] = {x, y, i};
}
}
}
int n;
scanf("%d", &n);
while (n--) {
int x, y;
scanf("%d %d", &x, &y);
x += B, y += B;
printf("%d\n", ans[x][y]);
}
return 0;
}
View Code
纯思维题。首先不考虑约束条件从$(0, 0)$到$(x, y)$的最短距离就是这两点间的曼哈顿距离，即$|x| + |y|$。分情况讨论：
- 如果$|x| = |y|$，那么很明显可以交替地往$x$的方向和往$y$的方向走，一共需要走$|x| + |y|$步可以从$(0, 0)$到$(x, y)$，恰好就是曼哈顿距离。
- 如果$|x| \ne |y|$，假设$|x| > |y|$（同理可证$|x| < |y|$的情况），由于有约束，对于$x$轴从$0$到$x$，至少需要走$2|x|-1$步。这是因为从$0$到$x$的曼哈顿距离是$|x|$，又由于每两步之间的走法不同，因此至少需要在这$x$步中加入$|x| - 1$种其他的走法。在$x$轴上因此从$0$走到$x$至少需要$2|x|-1$步。而这多余的$|x|-1$步可以用来在$y$轴上从$0$走向$y$，由于现在从$0$走向$x$的走法中任意两步均不同，从$0$走向$y$至少需要$|y| < |x|$即$|y| \leq |x|-1$步，因此这多出来的走法完全可以用来从$0$走到$y$。因此从$(0, 0)$到$(x, y)$至少需要$2|x|-1$步。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 void solve() {
5 int x, y;
6 scanf("%d %d", &x, &y);
7 x = abs(x), y = abs(y);
8 if (x == y) printf("%d\n", x + y);
9 else printf("%d\n", max(2 * x - 1, 2 * y - 1));
10 }
11
12 int main() {
13 int t;
14 scanf("%d", &t);
15 while (t--) {
16 solve();
17 }
18
19 return 0;
20 }
参考资料
Nebius Welcome Round Editorial：https://codeforces.com/blog/entry/113830
标签：King,dist,king,int,Lame,go,position,100 From： https://www.cnblogs.com/onlyblues/p/17215581.html