3 条题解

  • 0

    #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; }

    • 0
      @ 7 个月前
      #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<node> 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;
      }
      
      • -2

        绝对AC

        #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; }

        • 1

        信息

        ID
        103
        时间
        1000ms
        内存
        128MiB
        难度
        6
        标签
        递交数
        45
        已通过
        16
        上传者