Problem statement

https://leetcode.com/problems/shortest-path-to-get-all-keys/

Solution

One way to solve this problem is to use bfs: each state is (x, y, mask), where x, y are coordinates and mask is binary mask of visited nodes. Let us first find starting position and number of keys. Then we perform bfs: for each of 4 neighbors, we check if we can visit neighbor: if it has key, we can, and we need to update mask (note, that we can visit key if we already visited it before, if we have different mask). If we have lock and corresponding key is taken or we have empty cell or starting cell, we also can visit it. Finally, we check if candidate is in visited set and if it is not, we add it to queue and mark it as visited.

Complexity

Time complexity is O(mn2^A), where A is number of keys, space complexity is potentially the same to keep our queue.

Code

class Solution:
    def shortestPathAllKeys(self, grid):
        m, n = len(grid), len(grid[0])
        k = 0
        for i, j in product(range(m), range(n)):
            if grid[i][j] == "@": x, y = i, j
            if grid[i][j].isalpha(): k += 1
        
        queue = deque([(0,x,y,0)])
        visited = set()
        S1, S2, S3 = set("abcdef"), set("ABCDEF"), set(".@")
        
        while queue:
            steps, x, y, mask = queue.popleft()
            if mask == (1<<(k//2)) - 1: return steps
            
            for dx, dy in [[0,-1],[0,1],[1,0],[-1,0]]:
                if 0 <= x+dx < m and 0 <= y+dy < n:
                    cur, cand = grid[x+dx][y+dy], None
                    if cur in S1:
                        cand = (steps+1, x+dx, y+dy, (mask | 1<<(ord(cur)-97))) #update mask
                    if cur in S2 and mask & 1<<(ord(cur) - ord("A")) or cur in S3: 
                    #we can open lock or move
                        cand = (steps + 1, x+dx, y+dy, mask)
                        
                    if cand and cand[1:] not in visited:
                        visited.add(cand[1:])
                        queue.append(cand)
                            
        return -1

Remark

There is also bruteforce solution with complexity O(mn * A * A!), where we try to visit all A! order of keys.

Finally, there is Dijkstra solution: imagine graph with states (point of interest, mask), where we have 2A+1 points of interests: starting point, keys and lock and we have 2^A masks. Each node in this graph connected at most with 2A+1 other nodes: node is path between two points of interest, which do not have any other point of interest. So, this graph will have O(2^A * A) nodes and O(2^A * A^2) edges and we can perform Dijkstra on it with O(2^A * A^3) time. Final time complexity is O(2^A * A^3 + mnA), where O(mnA) time to construct graph. Space complexity is O(2^A * A^2) or O(2^A * A) if we compute edges on flight.