BOJ. Cubing (5373)

On this page

BOJ 5373: Cubing

Model and turn direction

Represent each sticker by its cubie position $(x,y,z)$ and outward normal. The axes are fixed to the cube: $+x$ points right, $+y$ points up, and $+z$ points toward the front. A sticker’s position has coordinates in $\{-1,0,1\}$ and its normal is one of the six signed axis vectors. The color belongs to the sticker, so turning a layer moves both its position and normal.

Use face order U, D, F, B, L, R, with initial colors white, yellow, red, orange, green, and blue, respectively. Each face also has a fixed row-down and column-right vector. For U, columns point along $+x$ and rows point along $+z$: row 0 is the back edge and row 2 is the front edge. Thus printing its cells in increasing row then column gives the required top-view orientation. The other face-local directions in the code define consistent coordinates for those stickers; they do not change the physical cube.

A command always names a face and a direction as seen while looking directly at that face from outside. Therefore + is a clockwise quarter-turn from that viewpoint and - is counterclockwise. In a right-handed coordinate system, positive rotation about an outward normal appears counterclockwise from outside. The implementation consequently rotates by $-90^\circ$ about the selected face’s outward normal for +, and by $+90^\circ$ for -.

For any sticker in the selected outer layer, rotate both its position $p$ and normal $v$ around the face’s unit normal $a$. A signed quarter-turn is computed as

$v' = a(a\cdot v) + s(a\times v),$

where $s=-1$ for clockwise and $s=+1$ for counterclockwise; the same formula applies to $p$. Since all components are in $\{-1,0,1\}$, this integer formula gives the exact quarter-turn without trigonometry. The new normal identifies the destination face, and dot products with that face’s row/column vectors recover its cell. Rotating every sticker in the layer also rotates the selected face itself, so no separate face-grid rotation or fragile strip-order cases are needed.

Complexity

There are always 54 stickers. Each command visits all 54 and performs a constant amount of integer arithmetic, so $q$ commands take $O(54q)=O(q)$ time and use $O(54)=O(1)$ space. Reading and printing the six-cell faces are likewise constant-size operations.

C++17

{% raw %}

#include <array>
#include <iostream>
#include <string>

using namespace std;

struct Vec {
    int x, y, z;
};

Vec operator+(Vec a, Vec b) { return {a.x + b.x, a.y + b.y, a.z + b.z}; }
Vec operator-(Vec a, Vec b) { return {a.x - b.x, a.y - b.y, a.z - b.z}; }
Vec operator*(int k, Vec a) { return {k * a.x, k * a.y, k * a.z}; }
int dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
Vec cross(Vec a, Vec b) {
    return {a.y * b.z - a.z * b.y,
            a.z * b.x - a.x * b.z,
            a.x * b.y - a.y * b.x};
}

struct Face {
    Vec normal;
    Vec rowDown;
    Vec colRight;
};

// Face order: U, D, F, B, L, R.
const array<Face, 6> faces = {{
    {{0, 1, 0}, {0, 0, 1}, {1, 0, 0}},   // U
    {{0, -1, 0}, {0, 0, -1}, {1, 0, 0}},  // D
    {{0, 0, 1}, {0, -1, 0}, {1, 0, 0}},   // F
    {{0, 0, -1}, {0, -1, 0}, {-1, 0, 0}}, // B
    {{-1, 0, 0}, {0, -1, 0}, {0, 0, 1}},  // L
    {{1, 0, 0}, {0, -1, 0}, {0, 0, -1}}  // R
}};

using Cube = array<array<array<char, 3>, 3>, 6>;

Vec positionOf(int face, int row, int col) {
    return faces[face].normal
         + (row - 1) * faces[face].rowDown
         + (col - 1) * faces[face].colRight;
}

int faceOf(Vec normal) {
    for (int f = 0; f < 6; ++f) {
        if (dot(faces[f].normal, normal) == 1) return f;
    }
    return -1;
}

void destination(Vec position, Vec normal, int& face, int& row, int& col) {
    face = faceOf(normal);
    Vec offset = position - faces[face].normal;
    row = dot(offset, faces[face].rowDown) + 1;
    col = dot(offset, faces[face].colRight) + 1;
}

Vec quarterTurn(Vec v, Vec axis, int sign) {
    return dot(axis, v) * axis + sign * cross(axis, v);
}

void turn(const Cube& cube, Cube& next, char faceName, char direction) {
    int f;
    switch (faceName) {
        case 'U': f = 0; break;
        case 'D': f = 1; break;
        case 'F': f = 2; break;
        case 'B': f = 3; break;
        case 'L': f = 4; break;
        default:  f = 5; break; // R
    }

    const Vec axis = faces[f].normal;
    const int sign = (direction == '+') ? -1 : 1;

    for (int sourceFace = 0; sourceFace < 6; ++sourceFace) {
        for (int row = 0; row < 3; ++row) {
            for (int col = 0; col < 3; ++col) {
                Vec position = positionOf(sourceFace, row, col);
                if (dot(position, axis) != 1) {
                    next[sourceFace][row][col] = cube[sourceFace][row][col];
                    continue;
                }

                Vec newPosition = quarterTurn(position, axis, sign);
                Vec newNormal = quarterTurn(faces[sourceFace].normal, axis, sign);
                int newFace, newRow, newCol;
                destination(newPosition, newNormal, newFace, newRow, newCol);
                next[newFace][newRow][newCol] = cube[sourceFace][row][col];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;
    while (testCases--) {
        array<Cube, 2> cube;
        int active = 0;
        const array<char, 6> initialColor = {'w', 'y', 'r', 'o', 'g', 'b'};
        for (int f = 0; f < 6; ++f) {
            for (int row = 0; row < 3; ++row) {
                for (int col = 0; col < 3; ++col) {
                    cube[active][f][row][col] = initialColor[f];
                }
            }
        }

        int commandCount;
        cin >> commandCount;
        while (commandCount--) {
            string command;
            cin >> command;
            turn(cube[active], cube[1 - active], command[0], command[1]);
            active = 1 - active;
        }

        for (int row = 0; row < 3; ++row) {
            for (int col = 0; col < 3; ++col) {
                cout << cube[active][0][row][col];
            }
            cout << '\n';
        }
    }
}

{% endraw %}