Problem: BOJ 3190 — Snake · 한국어 · 日本語
The snake starts at the upper-left cell facing right. At each second, it advances one cell. If the new head is outside the board or enters a cell still occupied by its body, the game ends at that second. An apple in the destination cell makes the snake grow; otherwise its tail moves forward by one cell. After completing a move, apply any direction change scheduled for that second.
Store the body in a deque from tail to head, and keep a boolean occupancy grid for constant-time collision checks. For a proposed move, first check whether its destination contains an apple. Normally an occupied destination is a collision, but there is one exception: when no apple is being eaten, the current tail vacates its cell during this move. Thus moving into that particular cell is legal. Remove the tail before inserting the new head in this case; when eating an apple, leave the tail in place and grow instead. Check wall bounds before indexing the grid.
The turn schedule is already chronological. After each successful move, process the turn whose time equals the current second: L rotates counterclockwise and D rotates clockwise. No turn is applied after a fatal move. If no collision occurs during all listed turns, continuing straight afterward eventually reaches a wall or the body.
Let S be the number of seconds actually simulated, including the final fatal move. Each move and each scheduled turn takes constant time, so the running time is O(S + K + N^2) including input and board initialization, where K is the number of turns. The space usage is O(N^2 + K) for the board and turn schedule; the deque contains at most N^2 cells.
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
#include <array>
#include <iostream>
#include <utility>
#include <vector>
#include <deque>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<bool>> apple(n, vector<bool>(n, false));
int appleCount;
cin >> appleCount;
for (int i = 0; i < appleCount; ++i) {
int row, column;
cin >> row >> column;
apple[row - 1][column - 1] = true;
}
int turnCount;
cin >> turnCount;
vector<pair<int, char>> turns(turnCount);
for (auto& [time, direction] : turns) cin >> time >> direction;
// Directions are right, down, left, up; the deque is tail to head.
constexpr array<int, 4> dr{0, 1, 0, -1};
constexpr array<int, 4> dc{1, 0, -1, 0};
vector<vector<bool>> occupied(n, vector<bool>(n, false));
deque<pair<int, int>> snake{{0, 0}};
occupied[0][0] = true;
int direction = 0;
int nextTurn = 0;
int seconds = 0;
while (true) {
++seconds;
const auto [headRow, headColumn] = snake.back();
const int nextRow = headRow + dr[direction];
const int nextColumn = headColumn + dc[direction];
if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n) break;
const bool eatingApple = apple[nextRow][nextColumn];
const auto [tailRow, tailColumn] = snake.front();
const bool enteringVacatingTail = !eatingApple &&
nextRow == tailRow &&
nextColumn == tailColumn;
if (occupied[nextRow][nextColumn] && !enteringVacatingTail) break;
if (eatingApple) {
apple[nextRow][nextColumn] = false;
} else {
snake.pop_front();
occupied[tailRow][tailColumn] = false;
}
snake.emplace_back(nextRow, nextColumn);
occupied[nextRow][nextColumn] = true;
if (nextTurn < turnCount && turns[nextTurn].first == seconds) {
direction = (direction + (turns[nextTurn].second == 'L' ? 3 : 1)) % 4;
++nextTurn;
}
}
cout << seconds << '\n';
return 0;
}