3 条题解

  • 0
    @ 2025-4-9 20:26:30

    #include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) using namespace std; typedef long long ll;

    struct node { int x, y, z, t; }t, cur;

    int dx[3][4] = { {-2, 0, 1, 0}, {-1, 0, 2, 0}, {-1, 0, 1, 0} }; int dy[3][4] = { {0, 1, 0, -2}, {0, 1, 0, -1}, {0, 2, 0, -1} }; int dz[3][4] = { {1, 2, 1, 2}, {0, 1, 0, 1}, {2, 0, 2, 0} }; int mp[9][9][3], d[3][3][3][4];

    void bfs(int x, int y, int z) { queue q; q.push({ x, y, z, 0 }); memset(mp, -1, sizeof mp); mp[x][y][z] = 0;

    while (!q.empty())
    {
        t = q.front(); q.pop(); cur.t = t.t + 1;
    
        rep(i, 0, 3)
        {
            cur.x = t.x + dx[t.z][i]; cur.y = t.y + dy[t.z][i]; cur.z = dz[t.z][i];
            if (cur.x < 0 || cur.x > 5 || cur.y < 0 || cur.y > 5) continue;
    
            if (mp[cur.x][cur.y][cur.z] == -1 || mp[cur.x][cur.y][cur.z] > cur.t)
                mp[cur.x][cur.y][cur.z] = cur.t, q.push(cur);
        }
    }
    

    }

    void init() { rep (k, 0, 2) rep (i, 0, 2) rep (j, 0, 2) { bfs(i + 3, j + 3, k); d[i][j][k][0] = mp[3][0][0]; d[i][j][k][1] = mp[3][3][0]; d[i][j][k][2] = mp[0][0][0]; d[i][j][k][3] = mp[0][3][0]; } }

    ll a, b; char op;

    ll calc(int c) { ll x = a / 3, y = b / 3; a %= 3, b %= 3; ll ans = d[a][b][c][1] + (x << 1) + (y << 1); if (y) ans = min(ans, d[a][b][c][0] + (x << 1) + (y - 1 << 1)); if (x) ans = min(ans, d[a][b][c][2] + (x - 1 << 1) + (y - 1 << 1)); return ans; }

    int main() { init(); while (cin >> op >> a >> b) { int c = op == 'U' ? 0 : op == 'V' ? 1 : 2; if (a > b) swap(a, b), c = c == 0 ? 0 : c == 1 ? 2 : 1; cout << calc(c) << '\n'; } return 0; }

    信息

    ID
    103
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    46
    已通过
    17
    上传者