Tunnel
SRM 765 · 2019-08-22 · by misof
Problem Statement
You are playing a game in which you control a spaceship ('v') flying through a tunnel. A sample level of the game looks as follows:
##..v..## ###.....# #####...# ####...## ###..#### #.......# #...#####
Above, '#' is a part of the tunnel wall and '.' is an empty space in the tunnel. At regular intervals, the spaceship makes a step forward (i.e., to the next row of the level). Before each step there is enough time to make rate keystrokes. There are two keys you can use to control your spaceship: the left and right arrows. Each keypress of each arrow moves the spaceship in the corresponding direction (within its current row, by a single step).
Is it possible to reach the last row of the level without hitting a wall? If no, return -1. If yes, return the smallest total number of keystrokes in which it can be done.
Constraints
- level will contain between 1 and 50 elements, inclusive.
- Each element of level will contain between 3 and 50 characters, inclusive.
- All elements of level will contain the same number of characters.
- For each i > 0, element i of level will be a valid level row. (A valid level row is a string of the following form: one or more '#' characters, one or more '.' characters, and again one or more '#' characters.)
- Element 0 of level will be a valid level row, with one '.' replaced by a 'v'.
- The tunnel will be contiguous. I.e., for each i > 0 there will be at least one index j such that neither level[i-1][j] nor level[i][j] is '#'.
- rate will be between 0 and 47, inclusive.
{"##..v..##",
"###.....#",
"#####...#",
"####...##",
"###..####",
"#.......#",
"#...#####"}
2
Returns: 3
The example tunnel from the problem statement. One optimal solution looks as follows: right, 3*forward, left, forward, left, 2*forward.
{"#.v.#",
"##..#",
"###.#",
"#...#"}
0
Returns: -1
You are not fast enough to press any keys. In this particular tunnel, your spaceship will eventually crash into a wall.
{"#v....#",
"###...#",
"#####.#"}
1
Returns: -1
One keystroke before each step is not enough to cross this tunnel.
{"#v....#",
"###...#",
"#####.#"}
2
Returns: 4
{"#...v.#"}
47
Returns: 0
This level is quite easy.
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Tunnel with a public method int minKeystrokes(vector<string> level, int rate) · 119 test cases · 2 s / 256 MB per case