自动搬运

查看原文

来自洛谷，原作者为

	Warfarin 用双脚丈量土地，将未知变为知识

搬运于2025-08-24 22:58:32，当前版本为作者最后更新于2024-05-24 20:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析

上来我们一眼丁真为搜索，但再仔细一看数据范围 $|x|,|y| \leq 10^{9}$。
显然，这需要我们来找找规律，既然求的是最小步数，我们就要思考，如何走效果最好，不难发现只有横着横向滚动和竖着竖向滚动时，两步就能走三格，这是最快的。
因此我们可以发现，图中某些坐标 $(x, y)$，如果满足 $x \equiv 0 \pmod 3$ 且 $y \equiv 0 \pmod 3$ 那么，它到达点 $(0,0)$ 的步数就为 $x \div 3 \times 2 + y \div 3 \times 2$。 可以发现，对于所有横纵坐标模 $3$ 为 $0$，且是立着的状态到终点的最小步数，我们能直接计算得出。
假设这些状态叫做合适点,那么我们只要让起点状态用最小步数走到合适点上，那么从起点到终点的距离就可以相加得出。所以，我们只用考虑起点周围的最近的合适点，这只需要我们将起点映射到一个 $4 \times 4$ 的格子中进行 bfs 即可。再求出该合适点到原点的步数并相加。

注意事项

建议在映射时，矩阵开大一些，避免数组越界。

AC 代码

#include <bits/stdc++.h>

#define ll long long
#define io cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define ri register int
#define lb long double

using namespace std;
const int N = 15;
typedef pair<int, int> qwq;
struct node
{
	int x, y, direction;
};
char op[2];
// 初始状态
int _x, _y;
//起点横纵坐标
int d[N][N][3];
//横坐标
//纵坐标
//方向
int next_x[3][4] = {{-2, 1, 0, 0}, {-1, 1, 0, 0}, {-1, 2, 0, 0}};
//下步横坐标变化
int next_y[3][4] = {{0, 0, -2, 1}, {0, 0, -1, 2}, {0, 0, -1, 1}};
//下步纵坐标变化
int next_direction[3][4] = {{2, 2, 1, 1}, {1, 1, 0, 0}, {0, 0, 2, 2}};
//下步方向变化
inline int bfs(int x, int y, int direction)
{
	memset(d, -1, sizeof d);
	d[x][y][direction] = 0;
	queue<node> q;
	q.push({x, y, direction});
	int ans = 1e10;
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		int x = t.x, y = t.y, z = t.direction;
		if (x % 3 == 0 && y % 3 == 0 && z == 0)
		{
			int nx = _x + x - 3, ny = _y + y - 3;
			int xd = nx / 3 * 2, yd = ny / 3 * 2;
			//还原回去
			if (xd < 0 || yd < 0)
				continue;
			//负数，说明非法，直接跳过
			ans = min(ans, d[x][y][z] + xd + yd);
			//更新合法答案
		}
		for (ri i = 0; i < 4; i++)
		{
			int a = x + next_x[z][i];
			int b = y + next_y[z][i];
			int _direction = next_direction[z][i];
			if (a < 0 || a >= N || b < 0 || b >= N)
				continue;
			if (d[a][b][_direction] == -1)
			{
				d[a][b][_direction] = d[x][y][z] + 1;
				q.push({a, b, _direction});
			}
		}
	}
	return ans;
}
int main()
{
	io;
	while (cin >> op >> _x >> _y && op[0] != EOF)
	{
		int z;
		if (op[0] == 'U')
			z = 0;
		else if (op[0] == 'H')
			z = 1;
		else
			z = 2;
		int sx = _x % 3 + 3;
		int sy = _y % 3 + 3;
		cout << bfs(sx, sy, z) << endl;
	}
	return 0;
}