Shortest Path To Get All Keys - Leetcode Solution

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 (Breadth-First 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:

1. 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.

2. 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.

3. We use a tuple (x, y, keys) to represent the current position of the player, i.e., the row x, column y of the maze and set of keys keys collected so far by the player.

4. 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.
   • If the destination is not reached, we continue with the modified BFS algorithm until we have explored all possible paths.

5. 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 python-based 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.

1