How do you solve Shortest Path to Get All Keys on LeetCode?

Shortest Path to Get All Keys (LeetCode #864) can be solved using Brute Force. The optimal approach is Brute Force with undefined time complexity and undefined space complexity. Key insight: The brute force approach involves exploring all possible paths from the starting point to collect all keys. We can use a breadth-first search (BFS) to traverse the grid, keeping track of the keys we collect along the way.

What is the time complexity of Shortest Path to Get All Keys?

The optimal solution for Shortest Path to Get All Keys runs in undefined time and uses undefined space. undefined

What algorithm or data structure is used to solve Shortest Path to Get All Keys?

Shortest Path to Get All Keys uses the following concepts: Array, Bit Manipulation, Breadth-First Search, Matrix. The recommended patterns to study are: .

#864

Shortest Path to Get All Keys

Hard

ArrayBit ManipulationBreadth-First SearchMatrix

LeetCode ↗

Approaches

💡

Intuition

Time Space

The brute force approach involves exploring all possible paths from the starting point to collect all keys. We can use a breadth-first search (BFS) to traverse the grid, keeping track of the keys we collect along the way.

⚙️

Algorithm

5 steps

1Step 1: Initialize a queue for BFS and start from the initial position '@'.
2Step 2: For each position, check all four possible directions (up, down, left, right).
3Step 3: If a cell contains a key, collect it and continue searching; if it contains a lock, ensure you have the corresponding key.
4Step 4: Keep track of visited positions and the keys collected.
5Step 5: Repeat until all keys are collected or all possibilities are exhausted.

solution.py33 lines

1from collections import deque
2
3def shortestPathAllKeys(grid):
4    m, n = len(grid), len(grid[0])
5    start = (0, 0)
6    total_keys = 0
7    for i in range(m):
8        for j in range(n):
9            if grid[i][j] == '@':
10                start = (i, j)
11            elif 'a' <= grid[i][j] <= 'f':
12                total_keys += 1
13    queue = deque([(start[0], start[1], 0, 0)])  # (x, y, steps, keys)
14    visited = set()
15    visited.add((start[0], start[1], 0))
16    while queue:
17        x, y, steps, keys = queue.popleft()
18        if keys == (1 << total_keys) - 1:
19            return steps
20        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
21            nx, ny = x + dx, y + dy
22            if 0 <= nx < m and 0 <= ny < n:
23                cell = grid[nx][ny]
24                if cell == '#': continue
25                new_keys = keys
26                if 'a' <= cell <= 'f':
27                    new_keys |= (1 << (ord(cell) - ord('a')))
28                if 'A' <= cell <= 'F' and not (keys & (1 << (ord(cell) - ord('A')))):
29                    continue
30                if (nx, ny, new_keys) not in visited:
31                    visited.add((nx, ny, new_keys))
32                    queue.append((nx, ny, steps + 1, new_keys))
33    return -1

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.