leetcode-graph

864. Shortest Path to Get All Keys.py

class Solution:
    """
    PQ:
        -Can I assume there's only one starting point in the given grid ?
        -at most 6 keys in the given grid --> "abcdef"
        -There could be mutiple pathes to find all keys with same minimum step.
    Thought Process:
        -grid--> apprently, it's a graph problem.
        -Each cell is node in the graph
        -edge is 4 directions
        -find the minimum moves to acquire all keys --> It's to find a shortest path problem given a graph.
        -For weighted graph, we think about, Dijkstra Algorithm(PQ+BFS)
        -For unweighted graph, we think about bfs, level by level. During bfs traversel, we keep track of step we move forward.
        
        BFS
            Step1:
                -find starting point
                -find number of keys we need to find, num_keys = 2, for example.
            Step2:
                -using bfs, level by level to collect keys, we progressively increase num_collected_keys. Once num_keys == num_collected_keys, mean we meet the goal, we return number of step we take. 
    
    Note:
        Becase we start from starting point to search, it guarantees that 我們一定從最小step慢慢到找到所有key.
    """
    directions = [(-1,0),(1,0),(0,1),(0,-1)]
    
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m = len(grid)
        n = len(grid[0])
        # step1: find starting point and number of keys we need to collect
        num_keys = 0
        start_i, start_j = None, None
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "@":
                    start_i, start_j = i, j
                elif grid[i][j] in "abcedf":
                    num_keys+=1
        # step2: do bfs from starting point
        steps = 0
        num_collected_keys = 0
        keys = "@.abcedf" # with this cell, we can pass without any restriction
        q = collections.deque([(start_i, start_j, steps, num_collected_keys, keys)])
        visited = set()
        while q:
            i, j, step, num_collected_keys, keys = q.popleft()
            # we find a key not a house 注意不能把重複拿到的key算兩遍, 所以要確寶這個keys(a, b, c, d, e, or, f)是之前沒拿過的
            if grid[i][j] in "abcdef" and grid[i][j].upper() not in keys:
                num_collected_keys+=1
                # we can walk over the room corresponding to the key we just got
                keys += grid[i][j].upper()
            if num_collected_keys == num_keys:
                return step
            
            for direction in self.directions:
                next_i, next_j = i+direction[0], j+direction[1]
                if 0<=next_i<m and 0<=next_j<n and grid[next_i][next_j] in keys:
                    state = (next_i, next_j, keys)
                    if state not in visited:
                        visited.add(state)
                        q.append((next_i, next_j, step+1, num_collected_keys, keys))

        return -1