Similar Problems
Similar Problems not available
Shortest Path To Get All Keys  Leetcode Solution
Companies:
LeetCode: Shortest Path To Get All Keys Leetcode Solution
Difficulty: Hard
Topics: matrix bitmanipulation array breadthfirstsearch
The problem Shortest Path to Get All Keys on LeetCode asks us to find the minimum number of moves required to collect all the keys in a given maze. Here is a detailed solution for this problem:
Approach:
The problem can be solved using BFS (BreadthFirst Search) algorithm on a modified maze (graph). The BFS algorithm will find the shortest path through the maze starting from the entrance or starting point. We need to keep track of the keys collected in order to calculate the total number of moves required to collect all the keys. We can use a hashset to record the keys found so far in order to be able to compare and update the number of steps taken or total cost to travel.
Algorithm:

At the start, we first identify the starting position and collect keys. We can represent the maze as a 2D array. However, since the maze is changing in every step, we will maintain a copy of the maze in each step.

Now, apply BFS algorithm on a modified maze. In order to solve the problem efficiently, we have to treat each state of the maze as a node in a graph.

We use a tuple
(x, y, keys)
to represent the current position of the player, i.e., the rowx
, columny
of the maze and set of keyskeys
collected so far by the player. 
The BFS algorithm works in the following manner:
 For each of the four (4) directions (up, down, left and right) do the following:
 Move the player to the adjacent cell, and update keys and steps taken so far accordingly:
 If the cell is not empty (i.e., either wall or door), we check if the player can move to that cell using current keys.
 If the adjacent cell contains a key, we update keys and move to the cell overwriting the key in the maze with
.
symbol.  If the adjacent cell contains a door that we can open with collected key(s), we update keys and move to the cell.
 If the adjacent cell is free, we move to the cell without any change to keys.
 We check if we have reached the destination where there are no more keys to collect, return the number of steps taken or total cost to get there.
 Move the player to the adjacent cell, and update keys and steps taken so far accordingly:
 If the destination is not reached, we continue with the modified BFS algorithm until we have explored all possible paths.
 For each of the four (4) directions (up, down, left and right) do the following:

In the end, if we reach the destination and all keys are collected, we return the number of steps taken (or cost) to get there, otherwise, we return
1
indicating there is no possible path to collect all keys.
Time Complexity:
The time complexity of the BFS algorithm is O(mn*2^k)
where m
and n
are the dimensions of the maze and k
is the number of keys. In the worst case scenario where we have to explore all possible paths, BFS algorithm will traverse through all the cells of the maze for each key, which can be 2^k
different combinations of keys, hence the time complexity.
Space Complexity:
The space complexity is O(mnk)
since we are storing m*n*2^k
nodes in the visited set and a maximum of k
keys that can be collected.
Here is the pythonbased implementation of the solution:
from collections import deque
class Solution:
def shortestPathAllKeys(self, grid: List[str]) > int:
m, n = len(grid), len(grid[0])
directions = [(0,1), (0,1), (1,0), (1,0)]
start_x, start_y = 1, 1
num_keys = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '@':
start_x, start_y = i, j
if grid[i][j].islower():
num_keys += 1
queue = deque([(start_x, start_y, '')])
# visited set
visited = set([(start_x, start_y, '')])
res = 0
while queue:
for _ in range(len(queue)):
x, y, keys = queue.popleft()
if len(keys) == num_keys:
return res
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
char = grid[nx][ny]
if char == '#' or (char.isupper() and char.lower() not in keys):
continue
new_keys = keys
if char.islower():
new_keys += char
if (nx, ny, new_keys) not in visited:
visited.add((nx, ny, new_keys))
queue.append((nx, ny, new_keys))
res += 1
return 1
The time complexity of the above solution can be reduced by applying memoization technique so that the algorithm does not repeat previously computed steps.
Shortest Path To Get All Keys Solution Code
1