TheQuestForGold
SRM 802 · 2021-03-18 · by misof
Problem Statement
DuckTales: The Quest for Gold is an old computer game. In the game, the player had to navigate the characters through various minigames. One of those is a cavern exploration game that inspired this problem.
The cave consists of a rectangular grid of chambers. Two chambers are adjacent if they are next to each other in the same row or column of the grid. When in the cave, the player may only move between adjacent chambers.
Some of those chambers contain pits. If the player enters such a chamber, they fall into the pit and die. The player's primary goal is to avoid dying.
Pits spread moisture. Therefore, each chamber that is directly adjacent to a pit will have slime on its walls. Slime does not occur anywhere else and therefore it can be used as a warning system: if the player sees the slime, they know that at least one of the adjacent chambers contains a pit.
At most one chamber contains treasure. The player's secondary goal is to find the treasure, if there is one.
The player has no knowledge of the cave. At the beginning of the game they are teleported into one of the chambers. When they find the treasure or give up, they are teleported back out.
You are shown the map of such a cave: a
If the player will find the treasure, return "gold" (quotes for clarity), if they won't, return "no gold".
Notes
- As implied by the input format, the player's starting chamber and the treasure chamber are always two distinct chambers.
- The chambers 'S' and 'T' do not contain a pit.
Constraints
- cave will contain between 1 and 50 elements, inclusive.
- Each element of cave will contain between 1 and 50 characters, inclusive.
- Each element of cave will contain the same number of characters.
- Each character in cave will be 'P', 'S', 'T', or '.'.
- There will be exactly one 'S'.
- There will be at most one 'T'.
{"S....",
".....",
"...T.",
"....."}
Returns: "gold"
No pits anywhere. The player will explore the cave and eventually find the treasure.
{"S....",
"...P.",
"..PTP",
"...P."}
Returns: "no gold"
The access to the treasure chest is completely blocked by the pits.
{"S....",
"..P.P",
".P.T.",
"....."}
Returns: "no gold"
There is no way to reach this treasure safely. To explain why, let's see what might happen to the player while exploring this cave. The player starts in the top left corner. They don't see any slime. They take one step to the right and discover another room without slime. They take another step to the right and discover a room with slime. At this moment, the player cannot go right or down from that room because they would risk dying. The only remaining option is to return by making a step left. Another way to reach an unexplored chamber is to make a step down. This discovers a second chamber with slime. ... and so on. The part of the map that will end up explored by the player is shown below, with '+' showing an explored chamber without slime and '*' an explored chamber with slime. ++*.. +*P.P *P.T. ..... We know that there are safe ways of accessing the rest of the cave (including the treasure) but the player does not know the map and they cannot move into any other chamber without risking death.
{"S....",
"P....",
"...T.",
"....."}
Returns: "no gold"
The player sees slime in their starting chamber. They are too afraid to move anywhere (they could die if they move), so the starting chamber will be the only explored chamber in this game. Again, the treasure remains undiscovered.
{"S....",
".....",
"PPP..",
".....",
".....",
".....",
"..PPP",
"..T.."}
Returns: "gold"
The player can navigate their way around these pits and eventually discover the treasure (in a chamber with slime).
{".......",
".......",
"..P.P..",
"..PPP..",
"..P.P..",
".......",
"..S...."}
Returns: "no gold"
There is no treasure, so the player will not find any treasure.
{".......",
".......",
"..P.P..",
"..PTP..",
"..P.P..",
".......",
"..S...."}
Returns: "no gold"
This is the same map as in the previous example, but now the middle chamber contains the treasure. The player will explore everything except for the pits and the room with the treasure. As the player isn't sure whether there is a treasure at all, they cannot step into the middle chamber: there can be a pit in that chamber and they could die.
Submissions are judged against all 79 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheQuestForGold with a public method string explore(vector<string> cave) · 79 test cases · 2 s / 256 MB per case