864. Shortest Path to Get All Keys

For 2-dimension bfs we use a set to avoid reentering a grid. For this problem, we sometime need to reenter a grid. We introduce one more dimension-state of acquired keys- to dedup.

at most 6 keys -> 6! states on the 3rd dimension. So each grid can be visited at most 64 times, thus total time complexity is O(k! * m * n) where k is the number of keys

class Solution(object):
    def shortestPathAllKeys(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        numOfKeys = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    starti = i
                    startj = j
                elif grid[i][j] in "abcdef":
                    numOfKeys += 1
        
        direc = [0,1],[0,-1],[1,0],[-1,0](/cocoder39/coco39_LC/wiki/0,1],[0,-1],[1,0],[-1,0)
        moves = set()
        queue = collections.deque([starti, startj, "", 0](/cocoder39/coco39_LC/wiki/starti,-startj,-"",-0))
        while queue:
            i, j, keys, stepCount = queue.popleft()

            if grid[i][j] in "abcdef" and grid[i][j] not in keys:
                keys += grid[i][j]
            
            if len(keys) == numOfKeys:
                return stepCount

            for x, y in direc:
                ni = i+x
                nj = j+y
                if 0 <= ni < m and 0 <= nj < n and (grid[ni][nj] in ".@abcdef" or grid[ni][nj].lower() in keys):
                    if (ni, nj, keys) not in moves:
                        moves.add((ni,nj,keys))
                        queue.append([ni, nj, keys, stepCount + 1])
                
        return -1

option 2: further optimization using bit to record each key state, so in total 2^k states rather than k! states in option 1. Total complexity is O(m * n * 2^k)

to acquire a key: keys |= 1 << (ord(grid[i][j]) - ord('a'))
to check if all keys have been acquired: if keys == (1 << numOfKeys) - 1:
to check if key has/ hasn't been acquired: (keys >> (ord(grid[ni][nj]) - ord('A'))) & 1 == 0

class Solution(object):
    def shortestPathAllKeys(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        numOfKeys = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    starti = i
                    startj = j
                elif grid[i][j] in "abcdef":
                    numOfKeys += 1
        
        direc = [0,1],[0,-1],[1,0],[-1,0](/cocoder39/coco39_LC/wiki/0,1],[0,-1],[1,0],[-1,0)
        moves = set()
        queue = collections.deque([starti, startj, 0, 0](/cocoder39/coco39_LC/wiki/starti,-startj,-0,-0))
        while queue:
            i, j, keys, stepCount = queue.popleft()

            if grid[i][j] in "abcdef":
                keys |= 1 << (ord(grid[i][j]) - ord('a'))
            
            if keys == (1 << numOfKeys) - 1:
                return stepCount

            for x, y in direc:
                ni = i+x
                nj = j+y
                if 0 <= ni < m and 0 <= nj < n:
                    if grid[ni][nj] == '#':
                        continue
                    elif grid[ni][nj] in "ABCDEF" and ((keys >> (ord(grid[ni][nj]) - ord('A'))) & 1 == 0):
                        continue
                    if (ni, nj, keys) not in moves:
                        moves.add((ni,nj,keys))
                        queue.append([ni, nj, keys, stepCount + 1])
                
        return -1

864. Shortest Path to Get All Keys - cocoder39/coco39_LC GitHub Wiki