Keys and Doors Maze
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are given a grid maze maze; character j of maze[i] is the cell in row i, column j:
| Char | Meaning |
|---|---|
S | start (exactly one) |
G | exit (exactly one) |
. | empty |
# | wall |
a – f | a key, picked up when you enter the cell |
A – F | a door, passable only while you hold the key of the same letter |
Each move goes one cell up, down, left or right, staying inside the grid. Keys are never used up. The same key or door
letter may appear in several cells. Return the minimum number of moves from S to G, or -1 if it is impossible.
Examples
| maze | result |
|---|---|
["S.A.G", "a####"] | 6 |
["S#G", ".#.", "..."] | 6 |
["SAG", "###"] | -1 |
Example 1 — Step down to key a (1), come back (2), then 4 more moves through door A to the exit.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(maze: string[]) → int
Constraints
-
maze.length,maze[i].length(all rows have the same length) mazecontains onlyS,G,.,#,a–f,A–F;SandGappear exactly once each.
Expected complexity
- Time
- O(R * C * 2^K)
- Space
- O(R * C * 2^K)
Examples
| maze | Expected |
|---|---|
["S.A.G","a####"] | 6 |
["S#G",".#.","..."] | 6 |
["SAG","###"] | -1 |
Hint
Hint
Where you can go depends on which keys you hold, so the state is (row, column, key set), with the key set as a 6-bit mask
— at most states. Every move costs 1, so BFS over these states (entering a key cell ORs its bit
into the mask; a door cell needs its bit) gives the answer the first time G is reached. Re-relaxing all states until
nothing changes is far too slow on long mazes.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 4 | verdict only |