Problem: BOJ 14499 — The Dice · 한국어 · 日本語
Keep the value on each of the six physical faces in a fixed orientation array: TOP, BOTTOM, NORTH, SOUTH, EAST, and WEST. The invariant is that every array entry always describes the face currently pointing in that direction. A roll changes only the four entries around its axis; the other two faces stay in place.
For an east roll, the old west face becomes the top, the old top becomes the east face, the old east face becomes the bottom, and the old bottom becomes the west face. A west roll is the reverse cycle. For a north roll, the old south face becomes the top, followed by the old top becoming north, old north becoming bottom, and old bottom becoming south. A south roll reverses that cycle. Save one face before assigning the four entries so each permutation uses constant time.
For each command, first check whether the adjacent cell is inside the board. If it is outside, ignore the command entirely: do not move the position, rotate the die, read or write a cell, or print anything. For a valid move, roll the die and synchronize its bottom with the destination cell. If the cell is nonzero, copy it to the bottom face and clear the cell; if it is zero, copy the bottom face into the cell. Then print the top face.
Each of the K commands takes constant time, so the total time complexity is O(K). The board uses O(NM) space, and the six face values use O(1) additional space.
C++17
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
#include <iostream>
using namespace std;
enum Face { TOP, BOTTOM, NORTH, SOUTH, EAST, WEST };
enum Direction { ROLL_EAST = 1, ROLL_WEST, ROLL_NORTH, ROLL_SOUTH };
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, row, col, k;
cin >> n >> m >> row >> col >> k;
int board[20][20] = {};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> board[i][j];
}
}
int die[6] = {};
for (int i = 0; i < k; ++i) {
int command;
cin >> command;
int next_row = row;
int next_col = col;
if (command == ROLL_EAST) {
++next_col;
} else if (command == ROLL_WEST) {
--next_col;
} else if (command == ROLL_NORTH) {
--next_row;
} else {
++next_row;
}
if (next_row < 0 || next_row >= n || next_col < 0 || next_col >= m) {
continue;
}
if (command == ROLL_EAST) {
const int old_west = die[WEST];
die[WEST] = die[BOTTOM];
die[BOTTOM] = die[EAST];
die[EAST] = die[TOP];
die[TOP] = old_west;
} else if (command == ROLL_WEST) {
const int old_east = die[EAST];
die[EAST] = die[BOTTOM];
die[BOTTOM] = die[WEST];
die[WEST] = die[TOP];
die[TOP] = old_east;
} else if (command == ROLL_NORTH) {
const int old_south = die[SOUTH];
die[SOUTH] = die[BOTTOM];
die[BOTTOM] = die[NORTH];
die[NORTH] = die[TOP];
die[TOP] = old_south;
} else {
const int old_north = die[NORTH];
die[NORTH] = die[BOTTOM];
die[BOTTOM] = die[SOUTH];
die[SOUTH] = die[TOP];
die[TOP] = old_north;
}
row = next_row;
col = next_col;
if (board[row][col] != 0) {
die[BOTTOM] = board[row][col];
board[row][col] = 0;
} else {
board[row][col] = die[BOTTOM];
}
cout << die[TOP] << '\n';
}
}