MazeWithKeys
SRM 736 *TCO19* · 2018-08-14 · by majk
Problem Statement
Bob is building a computer game. In the game the player's goal is to navigate his avatar through a maze to the exit. The floor of the maze is a square grid. Each cell of the maze is a corridor (passable), a wall (impassable), or a door (explained below). The avatar can move in the four cardinal directions.
Each door cell requires a different key. If the avatar doesn't have the key, the door cell behaves like a wall, but with the key it behaves like a corridor. Each corridor contains at most one key. Whenever the avatar enters a cell with a key, it picks up the key automatically. The avatar can carry arbitrarily many keys and use each key arbitrarily many times.
You are given the layout of the maze in the
- '.' represents a corridor without a key
- '#' represents a wall
- '*' represents the exit
- uppercase letters ('A'-'Z') represent doors
- lowercase letters ('a'-'z') represent a corridor that contains the corresponding key
Additional comments:
- There will always be exactly one exit.
- No two doors will share the same letter.
- Each key opens the door that corresponds to its uppercase version. E.g., key 'e' opens door 'E'.
- There may be arbitrarily many keys of each type (possibly even zero).
As you may have noticed, one thing is missing: the start. Bob needs to choose one of the empty corridors ('.' cells) as the start. When doing so, Bob has two constraints. First, the level must be solvable. Second, the level must not be boring. A level is boring if the player can reach the goal without opening any doors. Thus, Bob needs to choose the start in such a way that the avatar can reach the exit, but along its way it must open at least one door.
Compute and return the number of possible locations for the start.
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will contain between 1 and 50 characters, inclusive.
- All elements of a will have the same length.
- Each character in a will be '.', '#', '*', an uppercase letter, or a lowercase letter.
- There will be exactly one '*' in a.
- All uppercase letters in a will be distinct.
{"...A..a..*"}
Returns: 0
{".a.","#.#",".A*"}
Returns: 3
{"...a..A..*"}
Returns: 5
{"...a.b.A.B.*"}
Returns: 5
{"...a...A..b.B.*"}
Returns: 9
{"...#.A.",
".#B#.#.",
".#.#.#.",
".#.#.#.",
".#b#.#.",
"a#...#*"}
Returns: 10
In the diagram below, the cells marked by 1 are valid starting locations, as the puzzle is both solvable and not boring. Cells marked 2 are not valid locations for the start because from these cells the avatar can reach the exit without opening a door (i.e., the level would be boring). Cells marked 3 are not valid locations for the start because the level would be unsolvable: the avatar needs to open the 'B' door but cannot reach any 'b' key. 333#1A2 3#B#1#2 3#1#1#2 3#1#1#2 3#b#1#2 a#111#*
{"..*",
".a.",
"A.."}
Returns: 0
In this level there are no good locations for the start. Even though the avatar can pick up the 'a' key and open the 'A' door, this is never needed. In other words, regardless of where Bob places the start, there will always be a way to reach the goal without opening any doors, so the level will always be boring.
{".A*C.",
".#B#.",
".#.#.",
"a..b."}
Returns: 10
Any empty cell would make a good starting location, as the player needs to unlock either the door 'A' or the door 'B' to reach the exit. Note that there is no 'c' key even though there is a 'C' door.
{"a#a#*",
"#..#.",
"a..A."}
Returns: 4
Note that there are three copies of the key 'a'. Any one of them is enough to unlock the door.
Submissions are judged against all 91 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MazeWithKeys with a public method int startingPoints(vector<string> a) · 91 test cases · 2 s / 256 MB per case