Funcia
Lv.3bfsbitmaskgridshortest-path

Keys and Doors Maze

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

You are given a grid maze maze; character j of maze[i] is the cell in row i, column j:

CharMeaning
Sstart (exactly one)
Gexit (exactly one)
.empty
#wall
a – fa key, picked up when you enter the cell
A – Fa 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

mazeresult
["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

  • 1≤R=1 \le R = maze.length ≤100\le 100, 1≤C=1 \le C = maze[i].length ≤100\le 100 (all rows have the same length)
  • maze contains only S, G, ., #, a–f, A–F; S and G appear exactly once each.

Expected complexity

Time
O(R * C * 2^K)
Space
O(R * C * 2^K)

Examples

mazeExpected
["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 100⋅100⋅26100 \cdot 100 \cdot 2^6 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

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.