JumpingTiger
SRM 823 · 2022-02-01 · by misof
Problem Statement
To celebrate the Lunar New Year that starts the Year of the Tiger, the problems in this set feature tigers.
A tiger is travelling on a grid of unit squares. Some of those squares contain obstacles. The tiger may not enter those squares, but it can jump over them.
The tiger can move in steps. In each step it can move one square in one of the four cardinal directions. (I.e., from its current square to another square that shares a side with it.)
The tiger can also make jumps. Each jump must also be made in one of the four cardinal directions. When jumping, the tiger moves over one or more squares and then lands in the next one.
After a step the tiger is free to change its direction or to stop moving.
However, the tiger is heavy and after a jump it has a lot of inertia, which makes it impossible to change direction immediately. Thus, each jump must be followed either by a strictly shorter jump in the same direction, or by a step in the same direction.
(If the tiger follows a jump with a shorter jump, the second one does also count as a jump, and thus it must also be followed by a step or an even shorter jump in the same direction. Each of these steps or jumps counts as a separate action.)
The tiger is not allowed to leave the grid. If a step or jump would lead to the tiger having to leave the grid, the tiger is not allowed to perform it.
You are given the
There is exactly one 'T' and exactly one 'L'. Both of these squares count as empty squares. The tiger may enter and leave each empty square, including these two, arbitrarily many times during its travels.
Calculate and return the smallest possible total number of actions (steps + jumps) the tiger needs to perform in order to reach the lair and stop there. Return -1 if this goal cannot be reached.
Constraints
- plan will contain between 1 and 50 elements, inclusive.
- Each element of plan will contain between 1 and 50 characters, inclusive.
- Each element of plan will contain the same number of characters.
- Each character in plan will be one of ".#TL".
- plan will contain exactly one 'T'.
- plan will contain exactly one 'L'.
{"T.######",
"#..#####",
"##..####",
"###..###",
"####..##",
"#####..#",
"######..",
"#######L"}
Returns: 14
The tiger takes alternate steps "right" and "down" until it reaches the lair.
{"T.######",
"#..#####",
"##..####",
"###..###",
"####..##",
"#####..#",
"######..",
".######L"}
Returns: 14
The extra empty square in the bottom left corner does not help. The tiger is not allowed to jump there from its current location because the next step or jump would then take it outside the grid.
{"T.######",
"#..#####",
"##..####",
"###..###",
"####..##",
"#####..#",
".#####..",
".######L"}
Returns: 6
Now the tiger is able to reach the bottom left corner from its starting location by jumping to the penultimate row and then making a step. At this moment, the tiger cannot just jump to its lair: remember that the tiger is required to actually stop at the lair. However, the tiger now has another, slightly longer way to reach its lair. From the bottom left corner of the grid it can now take a step up, then jump to the penultimate column, follow that jump by a step to the right, and finally take a step down to reach the lair.
{"T.######",
"#..#####",
"##..####",
"###..###",
"####..##",
"#####..#",
".#####..",
".#####.L"}
Returns: 4
Now we are good, the tiger can make a jump down followed by a step and then a jump right followed by a step.
{".##.",
"#L##",
"####",
".#T#"}
Returns: -1
The tiger has no valid move: the only way to reach a square without an obstacle is a jump left, but that one would have to be followed by another move that would take the tiger outside the grid.
{"T", "#", "#", "L", "#", "#", ".", "."}
Returns: -1
The tiger can jump onto its lair but it cannot reach it in a way that would allow it to stop there.
Submissions are judged against all 99 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class JumpingTiger with a public method int travel(vector<string> plan) · 99 test cases · 2 s / 256 MB per case