Leetcode 2812. Find the Safest Path in a Grid

📅2023-08-13🧐251

https://leetcode.com/problems/find-the-safest-path-in-a-grid/

We can use BFS and heap queue(priority queue) to solve this problem. It also belongs to a shortest path problem. So Dijkstra's algorithm is a very good approach for this problem.

  1. We need to find out all the thieives
  2. Pre-calculate the distance from a slot to a thief, if there are multiple thieves, we need to calculate all the distance and use the minimum one.
  3. Create a max-heap to find the most safe path, so we can get maximum safeness factor form that path.
from heapq import heappush, heappop
from collections import deque

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] or grid[n - 1][n - 1]:
            return 0

        t = set()
        for row in range(n):
            for col in range(n):
                if grid[row][col] == 1:
                    t.add((row, col))

        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        distance = [[float('inf')] * n for _ in range(n)]

        for tx, ty in t:
            seen = set()
            tq = deque([(tx, ty, 0)])
            while tq:
                row, col, d = tq.popleft()
                if (row, col) in seen:
                    continue
                
                seen.add((row, col))

                if d >= distance[row][col]:            
                    continue
                distance[row][col] = d

                for r, c in dirs:
                    nr, nc = row + r, col + c
                    if nr < 0 or nc < 0 or nr >= n or nc >= n or (nr, nc) in seen:
                        continue
                    tq.append((nr, nc , d + 1))

        q = [(-distance[0][0], 0, 0)]
        seen = set()
        seen.add((0, 0))
        ans = float('inf')
        while q:
            d, row, col = heappop(q)
            ans = min(ans, -d)
            if row == n - 1 and col == n - 1:
                return ans
            for r, c in dirs:
                nr, nc = row + r, col + c
                if 0 <= nr < n and 0 <= nc < n:
                    if (nr, nc) in seen:
                        continue

                    heappush(q, (-distance[nr][nc], nr, nc))
                    seen.add((nr, nc))