Leetcode # 2812. Find the Safest Path in a Grid

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

Solution

計算 min_dis (queue/BFS)

m := len(grid)
n := len(grid[0])
min_dis[i][j] := min([manhattan_distance((i, j), thief) for thief in thieves])

以 (i, j) 為起點，計算整張 grid 的 min_dis[i][j]
for i in range(m):
  for j in range(n):
    compute min_dis[i][j]
time complexity:O(m * n * len(thieves))

使用 queue/BFS 以 thieves 為起點遍歷整張 grid
time complexity: O(m * n)

找到 maximum safeness factor 的 path

safeness factor := min([min_dis[i][j] for i, j in path])
目標：Return the maximum safeness factor of all paths from (0, 0) to (m – 1, n – 1)

找出 max([min_dis[i][j] for i, j in path]) 最小的 path
找出 sum([min_dis[i][j] for i, j in path]) 最小的 path
從 (0, 0) 走到 (m, n) 只會向右或向下走

正確的 path 找法：
1. 走法可以任意上下左右
2. 令 maximum safeness factor 為 d
⇒ 找不到一條 any(min_dis[i][j] > d for i, j in path) == True 的path
⇔ all(min_dis[i][j] <= d for path in paths for i, j in path)
⇔ 最遠只能和 thieves 保持距離 d 以下（⇒ d 越大越困難）

寫一個can_find_a_path(safeness_factor_greater_than)
(time complexity: O(m * n))
能用來判斷能不能找到
all(min_dis[i][j] > safeness_factor_greater_than for i, j in path) == True 的path

再用 binary search 找出能使can_find_a_path(d)為False的d
因為 d 越大越困難，我們要找的 d 能滿足：
1. all(can_find_a_path(_d) == True for _d in range(d)) == True
2. all(can_find_a_path(_d) == False for _d in range(d, m + n + 1)) == True

Time Complexity: O((m * n) + (m * n) * log(m + n)) = O(m * n * log(m + n))
Space Complexity: O(m * n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    manhattan = lambda a, b, x, y: abs(a - x) + abs(b - y)
    thieves = [(j, i, 0) for i in range(m) for j in range(n) if grid[i][j] == 1]
    min_dis = [[None] * n for _ in range(m)]
    queue = collections.deque(thieves)
    while queue:
      j, i, dis = queue.popleft()
      if min_dis[i][j] is not None: continue
      min_dis[i][j] = dis
      for dr in direct:
        _i, _j = i + dr[1], j + dr[0]
        if 0 <= _i < m and 0 <= _j < n:
          queue.append((_j, _i, dis + 1))

    def can_find_a_path(safeness_factor_greater_than):
      footprint = [[False] * n for _ in range(m)]
      def goto(i, j):
        footprint[i][j] = True
        if min_dis[i][j] <= safeness_factor_greater_than: return False
        if i == m - 1 and j == n - 1: return True
        for dr in direct:
          _i, _j = i + dr[1], j + dr[0]
          if 0 <= _i < m and 0 <= _j < n and not footprint[_i][_j]:
            if goto(_i, _j): return True
        return False
      return goto(0, 0)

    left, right = 0, (m + n)
    while left < right:
      mid = (left + right) // 2
      result = can_find_a_path(mid)
      if result:
        left = mid + 1 
      else:
        right = mid
    return left

 

Last Updated on 2023/09/09 by A1go

目錄

→ 目錄
Bitnami