⚡Flashcard Drill➔
NeetCode #632LC-2812MediumAdvanced Graphs
← Back to All Problems

#632 · #2812 · Find the Safest Path in a Grid(找出最安全路径)

📌 Problem Statement & Constraints

You are given an n x n grid where 1 is a thief and 0 is empty. The safeness factor of a path is the minimum Manhattan distance from any cell on the path to the nearest thief. Return the maximum safeness factor over all paths from the top-left to the bottom-right. Constraints: 1 <= n <= 400.

💡 Core Algorithmic Approaches

  1. Step 1: multi-source BFS from every thief computes each cell's distance to the nearest thief.
  2. Step 2: run a max-heap Dijkstra where the key is the minimum distance along the path.
  3. This is the same "maximise the bottleneck" template as Path With Minimum Effort.
  4. The two-phase structure separates the distance computation from the path search.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        from collections import deque
        import heapq
        n = len(grid)
        if grid[0][0] or grid[n - 1][n - 1]:
            return 0                       # start or end occupied by a thief

        # phase 1: distance to the nearest thief (multi-source BFS)
        dist = [[-1] * n for _ in range(n)]
        q = deque()
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dist[i][j] = 0
                    q.append((i, j))
        while q:
            r, c = q.popleft()
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))

        # phase 2: maximise the minimum safeness along the path
        h = [(-dist[0][0], 0, 0)]
        seen = {(0, 0)}
        while h:
            neg, r, c = heapq.heappop(h)
            cur = -neg
            if r == n - 1 and c == n - 1:
                return cur
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    heapq.heappush(h, (-min(cur, dist[nr][nc]), nr, nc))
        return 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 log n): the BFS is linear and the Dijkstra pushes each cell once.
💾 Space Complexity
O(n^2) for the distance grid and the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Computing the distance per path: O(paths * n^2); the precomputed grid makes it O(1) per cell.
  • Using a min-heap for the path search: the bottleneck must be maximised.
  • Summing the safeness values: the path's safeness is its minimum.
  • Forgetting the start/end thief check: a thief on the start or end makes the answer 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems