FunctionRacerProblemsRace

Collect Every Key

HardGraphsPython, JavaScript, TypeScript, Java, C++

grid is a map, one string per row: # is a wall, . is open floor, @ is where you start, a lowercase letter is a key and an uppercase letter is a lock.

One move goes up, down, left or right, never into a wall and never off the map. Stepping on a key picks it up. A lock can be entered only with the key of the same letter in hand, and stays open after that.

Return the fewest moves needed to pick up every key, or -1 if that cannot be done. No letter appears twice in the same case.

Example 1

grid ["@.a","##A","b.."]
returns 6

Two moves right for key a, down through lock A, then along the bottom row to key b: 2 + 4 moves.

Example 2

grid ["a@.b"]
returns 4

Key a is one move left and key b then three moves right. The other order would take five.

Example 3

grid ["@Ab"]
returns -1

Key b lies behind lock A, and there is no key a anywhere.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems