2812. Find the Safest Path in a Grid

link

Multisource bfs + dijkstra

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        
        m = len(grid)
        n = len(grid[0])
        
        dq = deque()
        
        # from every thief node
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dq.append((i,j))

        # make the distance matrix
        current = 0
        s = set()
        
        while dq:
            
            lens = len(dq)
            
            for _ in range(lens):
                i, j = dq.popleft()
                
                if (i, j) in s:
                    continue
                    
                s.add((i, j))
                
                grid[i][j] = current
                
                for x, y in [(0,1),(0,-1),(1,0),(-1,0)]:
                    if not (0 <= i + x < m and 0 <= j + y < n):
                        continue
                    dq.append((i+x, j+y))
                    
            current += 1

        # dijkstra
        h = [(-grid[0][0], 0, 0)]
        
        ss = set()
        
        while h:
            lens = len(h)
            
            for _ in range(lens):
                res, i, j = heappop(h)
                
                if (i, j) in ss:
                    continue
                    
                ss.add((i, j))
                
                if res == 0:
                    continue
                    
                if i == m - 1 and j == n - 1:
                    return -res
                    
                for x, y in [(0,1),(0,-1),(1,0),(-1,0)]:
                    if not (0 <= i + x < m and 0 <= j + y < n):
                        continue
                    heappush(h, ( max(res, -grid[i+x][j+y]) ,i+x, j+y))
                
        return 0