题解：P10493 Bloxorz II

· · 题解

思路分析

上来我们一眼丁真为搜索，但再仔细一看数据范围 |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;
}