hardGraphsAI-applied~40 min
Agent Collects Every Key in a Gridworld
A planning agent navigates a gridworld. Lowercase cells are API keys; uppercase cells are locked doors that need the matching key. Find the fewest moves to acquire every key.
Problem
Given a grid where '@' is the start, '.' is empty, '#' is a wall, lowercase letters are keys, and uppercase letters are locks, you move in 4 directions one cell per step. You may pass a lock only after collecting its lowercase key. Return the fewest moves to collect all keys, or -1 if impossible.
Input
An array of equal-length strings forming the grid.
Output
An integer: minimum moves to collect all keys, or -1.
Constraints
- 1 <= grid rows, cols <= 30
- There are between 1 and 6 keys, each a distinct letter a..f, with matching locks present at most once.
- Exactly one '@' start cell.
Examples
Example 1
Input
grid = ["@.a..","###.#","b.A.B"]
Output
8
Collect 'a', open 'A', collect 'b' in 8 moves.
Example 2
Input
grid = ["@..aA","..B#.","....b"]
Output
6
Collect 'a' then 'b' in 6 moves.