#864

Hard

LeetCode Problem Workspace

Shortest Path to Get All Keys

Find the minimum steps to collect all keys in a grid using BFS and bitmasking, handling locks efficiently.

array bit manipulation breadth first search matrix

Problem Statement

You are given an m x n grid where '@' marks your starting position, '.' are empty spaces, lowercase letters are keys, and uppercase letters are locks. You can move in four directions and cannot pass through walls marked with '#'. Each move covers one cell.

Your goal is to collect all keys in the grid in the minimum number of steps. You can pick up a key by walking over it and can only pass through a lock if you have its matching key. Return the fewest steps required, or -1 if collecting all keys is impossible.

Examples

Example 1

Input: grid = ["@.a..","###.#","b.A.B"]

Output: 8

Note that the goal is to obtain all the keys not to open all the locks.

Example 2

Input: grid = ["@..aA","..B#.","....b"]

Output: 6

Example details omitted.

Example 3

Input: grid = ["@Aa"]

Output: -1

Example details omitted.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] is either an English letter, '.', '#', or '@'.
There is exactly one '@' in the grid.
The number of keys in the grid is in the range [1, 6].
Each key in the grid is unique.
Each key in the grid has a matching lock.

Solution Approach

Use BFS with State Tracking

Perform a breadth-first search from the starting position, tracking not just coordinates but also the set of collected keys using a bitmask. Each BFS node represents a unique combination of position and keys.

Handle Locks with Bitmask Checks

Before moving into a cell with a lock, check if the corresponding bit in the key bitmask is set. This ensures only valid paths are explored, avoiding unnecessary BFS expansions that would fail due to missing keys.

Optimize State Memory

Maintain a visited set keyed by both position and current key bitmask to prevent revisiting states. This reduces redundant exploration and guarantees the algorithm runs within manageable space despite multiple key combinations.

Complexity Analysis

Metric	Value
Time	O(RC(2\mathcal{A} + 1) + \mathcal{E} \log \mathcal{N})
Space	O(\mathcal{N})

Time complexity is O(RC(2^A + 1) + E log N) due to BFS across R*C positions with up to 2^A key combinations, where A is number of keys. Space complexity is O(N) for storing visited states for each position and key bitmask.

What Interviewers Usually Probe

Expect questions on BFS combined with bitmasking for state representation.
Watch for cases where multiple paths reach the same cell with different keys.
Clarify handling of unreachable keys due to locked doors blocking all paths.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include the current key state in the visited set, causing cycles or incorrect answers.
Trying to brute-force paths without pruning, leading to exponential time explosion.
Incorrectly assuming keys can be collected in any order without considering locks.

Follow-up variants

Grid sizes larger than 30x30 with more keys and locks to stress BFS efficiency.
Grids where some keys are completely inaccessible unless others are collected first.
Variants with multiple starting points requiring coordinated key collection.

FAQ

How does bit manipulation help in Shortest Path to Get All Keys?

Each key is represented as a bit in an integer, allowing efficient checks and updates for collected keys, crucial for BFS state tracking.

What happens if a key is behind a lock?

You cannot pass through the lock until the corresponding key is collected, so BFS must explore alternative paths until the key is obtained.

Can we revisit a cell after picking up keys?

Yes, revisiting is allowed but must consider the current key bitmask to avoid redundant exploration of already visited states.

What is the maximum number of keys supported?

The problem restricts keys to a maximum of 6, which fits within a 6-bit integer for efficient bitmask representation.

Why BFS is preferred over DFS for this problem?

BFS ensures the minimum steps are found first, whereas DFS might explore longer paths and fail to guarantee the shortest path to collect all keys.

terminal

Solution

Solution 1: State Compression + BFS

According to the problem description, we need to start from the initial position, move in four directions (up, down, left, right), collect all keys, and finally return the minimum number of moves required to collect all keys. If it is not possible to collect all keys, return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        # Find the starting point (si, sj)
        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')
        # Count the number of keys
        k = sum(v.islower() for row in grid for v in row)
        dirs = (-1, 0, 1, 0, -1)
        q = deque([(si, sj, 0)])
        vis = {(si, sj, 0)}
        ans = 0
        while q:
            for _ in range(len(q)):
                i, j, state = q.popleft()
                # If all keys are found, return the current step count
                if state == (1 << k) - 1:
                    return ans

                # Search in the four directions
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    nxt = state
                    # Within boundary limits
                    if 0 <= x < m and 0 <= y < n:
                        c = grid[x][y]
                        # It's a wall, or it's a lock but we don't have the key for it
                        if (
                            c == '#'
                            or c.isupper()
                            and (state & (1 << (ord(c) - ord('A')))) == 0
                        ):
                            continue
                        # It's a key
                        if c.islower():
                            # Update the state
                            nxt |= 1 << (ord(c) - ord('a'))
                        # If this state has not been visited, enqueue it
                        if (x, y, nxt) not in vis:
                            vis.add((x, y, nxt))
                            q.append((x, y, nxt))
            # Increment the step count
            ans += 1
        return -1

Continue Practicing

#1284 minimum number of flips to convert binary matrix to zero matrix #861 score after flipping matrix #832 flipping an image