魔方 - 题目列表

题意

给定三阶魔方六个面的当前状态，以及一串只包含 1..4 的操作。

每种操作都表示一种固定的转动。执行完整个操作串后，输出六个面的最终状态。

思路

先看一个同样直接模拟的对拍版本：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include <bits/stdc++.h>
using namespace std;

struct Cube {
    int a[6][3][3];
};

Cube move_one(const Cube &cube, int op) {
    Cube next = cube;

    if (op == 1 || op == 2) {
        int order1[4] = {0, 5, 1, 4};
        int order2[4] = {0, 4, 1, 5};
        int *order = (op == 1 ? order1 : order2);
        for (int idx = 0; idx < 4; ++idx) {
            int from = order[(idx + 1) % 4];
            int to = order[idx];
            for (int r = 0; r < 3; ++r) {
                next.a[to][r][2] = cube.a[from][r][2];
            }
        }

        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                if (op == 1) {
                    next.a[3][r][c] = cube.a[3][2 - c][r];
                } else {
                    next.a[3][r][c] = cube.a[3][c][2 - r];
                }
            }
        }
    } else {
        int order1[4] = {0, 2, 1, 3};
        int order2[4] = {0, 3, 1, 2};
        int *order = (op == 3 ? order1 : order2);
        for (int idx = 0; idx < 4; ++idx) {
            int from = order[(idx + 1) % 4];
            int to = order[idx];
            for (int c = 0; c < 3; ++c) {
                next.a[to][0][c] = cube.a[from][0][c];
            }
        }

        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                if (op == 3) {
                    next.a[4][r][c] = cube.a[4][2 - c][r];
                } else {
                    next.a[4][r][c] = cube.a[4][c][2 - r];
                }
            }
        }
    }

    return next;
}

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

    string steps;
    cin >> steps;

    Cube cube;
    string row;
    for (int f = 0; f < 6; ++f) {
        for (int r = 0; r < 3; ++r) {
            cin >> row;
            for (int c = 0; c < 3; ++c) {
                cube.a[f][r][c] = row[c] - '0';
            }
        }
    }

    for (char ch : steps) {
        cube = move_one(cube, ch - '0');
    }

    for (int f = 0; f < 6; ++f) {
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                cout << cube.a[f][r][c];
            }
            cout << '\n';
        }
    }
    return 0;
}

这题没有复杂的算法，关键是别把转动关系写错。

可以把六个面分别看成六个 3 x 3 数组。每次操作都拆成两部分：

把四个相邻面的某一行或某一列做循环搬运。
把被转动的那个面自身顺时针或逆时针旋转九十度。

只要把四种操作分别写成四个函数，逻辑就会很清楚：

1：右侧面顺时针转。
2：右侧面逆时针转。
3：上侧面顺时针转。
4：上侧面逆时针转。

代码实现时，先用临时数组存住会被覆盖的一列或一行，再完成四个面的循环赋值，最后单独旋转本面。

由于题目原始图示目前无法通过仓库脚本抓取，本题解采用的是已经通过公开样例和随机对拍验证的操作映射。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166#include <bits/stdc++.h>
using namespace std;

int front_face[4][4], back_face[4][4], left_face[4][4];
int right_face[4][4], up_face[4][4], down_face[4][4];

void rotate_right_clockwise() {
    int tmp[4];
    for (int i = 1; i <= 3; ++i) {
        tmp[i] = front_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        front_face[i][3] = down_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        down_face[i][3] = back_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        back_face[i][3] = up_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        up_face[i][3] = tmp[i];
    }

    int old_face[4][4];
    memcpy(old_face, right_face, sizeof(old_face));
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            right_face[i][j] = old_face[4 - j][i];
        }
    }
}

void rotate_right_counterclockwise() {
    int tmp[4];
    for (int i = 1; i <= 3; ++i) {
        tmp[i] = front_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        front_face[i][3] = up_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        up_face[i][3] = back_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        back_face[i][3] = down_face[i][3];
    }
    for (int i = 1; i <= 3; ++i) {
        down_face[i][3] = tmp[i];
    }

    int old_face[4][4];
    memcpy(old_face, right_face, sizeof(old_face));
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            right_face[i][j] = old_face[j][4 - i];
        }
    }
}

void rotate_up_clockwise() {
    int tmp[4];
    for (int i = 1; i <= 3; ++i) {
        tmp[i] = front_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        front_face[1][i] = left_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        left_face[1][i] = back_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        back_face[1][i] = right_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        right_face[1][i] = tmp[i];
    }

    int old_face[4][4];
    memcpy(old_face, up_face, sizeof(old_face));
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            up_face[i][j] = old_face[4 - j][i];
        }
    }
}

void rotate_up_counterclockwise() {
    int tmp[4];
    for (int i = 1; i <= 3; ++i) {
        tmp[i] = front_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        front_face[1][i] = right_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        right_face[1][i] = back_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        back_face[1][i] = left_face[1][i];
    }
    for (int i = 1; i <= 3; ++i) {
        left_face[1][i] = tmp[i];
    }

    int old_face[4][4];
    memcpy(old_face, up_face, sizeof(old_face));
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            up_face[i][j] = old_face[j][4 - i];
        }
    }
}

void read_face(int face[4][4]) {
    string row;
    for (int i = 1; i <= 3; ++i) {
        cin >> row;
        for (int j = 1; j <= 3; ++j) {
            face[i][j] = row[j - 1] - '0';
        }
    }
}

void print_face(int face[4][4]) {
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            cout << face[i][j];
        }
        cout << '\n';
    }
}

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

    string steps;
    cin >> steps;
    read_face(front_face);
    read_face(back_face);
    read_face(left_face);
    read_face(right_face);
    read_face(up_face);
    read_face(down_face);

    for (char ch : steps) {
        if (ch == '1') {
            rotate_right_clockwise();
        } else if (ch == '2') {
            rotate_right_counterclockwise();
        } else if (ch == '3') {
            rotate_up_clockwise();
        } else if (ch == '4') {
            rotate_up_counterclockwise();
        }
    }

    print_face(front_face);
    print_face(back_face);
    print_face(left_face);
    print_face(right_face);
    print_face(up_face);
    print_face(down_face);
    return 0;
}

复杂度

设操作串长度为 L，时间复杂度 $O(L)$ ，空间复杂度 $O(1)$ 。

总结

这类题的重点不是算法套路，而是把状态拆清楚。把每种转动统一写成“搬一圈 + 转一面”，代码会稳定很多，也更容易自己检查。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

魔方

目录

题意

思路

代码

复杂度

总结

一图流解析