This problem combines distance field calculation with a "bottleneck path" problem, making it a classic candidate for graph traversal optimizations.

Brute Force Approach for Find the Safest Path in a Grid

A naive brute force approach attempts to evaluate every possible path from the start to the end to find the one with the highest safeness factor.

1. Calculate Distances: Iterate through every cell $(r, c)$ in the grid. For each cell, iterate through every thief to find the minimum Manhattan distance.
2. Find Paths: Use Depth First Search (DFS) to explore all simple paths from $(0, 0)$ to $(n-1, n-1)$.
3. Evaluate: For each path found, determine the minimum distance value among all cells in that path. Track the maximum of these minimums.

python
# Pseudo-code for Naive Approach
def brute_force(grid):
    # 1. Calculate distances O(N^4)
    dist_matrix = calculate_all_distances_naive(grid) 
    
    max_safeness = 0
    
    # 2. DFS to find all paths (Exponential)
    def dfs(r, c, current_path_min):
        if r == n-1 and c == n-1:
            max_safeness = max(max_safeness, current_path_min)
            return
        
        for neighbor in neighbors(r, c):
            new_min = min(current_path_min, dist_matrix[neighbor])
            dfs(neighbor, new_min)
            
    dfs(0, 0, dist_matrix[0][0])
    return max_safeness

Complexity Analysis: The naive distance calculation takes $O(N^2 \cdot (\text{number of thieves}))$, which can be $O(N^4)$ in the worst case. Furthermore, the number of paths in a grid is exponential relative to $N$. With $N=400$, an exponential solution will immediately result in a Time Limit Exceeded (TLE).

Core Insight for Find the Safest Path in a Grid

The solution requires two distinct phases, both relying on graph traversal principles.

Phase 1: Efficient Distance Calculation (Multi-Source BFS) The brute force method calculates distances in $O(N^4)$. However, we can calculate the distance from every cell to its nearest thief in $O(N^2)$ using Multi-Source Breadth-First Search. Instead of starting a BFS from one node, we initialize the queue with all thief coordinates simultaneously. The BFS expands layer by layer; the first time a cell is visited, it is guaranteed to be reached via the shortest path from the closest thief. This creates a "distance field" grid.

Phase 2: Maximizing the Minimum Value (Modified Dijkstra) Once we have the distance grid, the problem becomes finding a path from start to end such that the minimum value observed on the path is maximized. This is a variation of the Shortest Path problem. In standard Dijkstra, we greedily pick the path with the smallest total cost. Here, we greedily pick the path with the highest bottleneck capacity.

We use a Priority Queue (Max-Heap) to store states (safeness, r, c). The safeness value represents the minimum distance encountered so far on the path from the start to (r, c). By always expanding the node with the highest current safeness, we ensure that when we reach the target, we have found the optimal path.

Visual Description: Imagine the distance grid as a terrain map where high distance values represent peaks and low values (near thieves) represent valleys. You are trying to drive from the top-left to the bottom-right while staying at the highest possible elevation. You start at your current elevation. At every step, you look at all reachable neighbors and move to the one that forces you to descend the least. A Max-Heap allows you to essentially "flood" the terrain from the highest accessible points downwards until you reach the destination.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

1. Pre-computation (Multi-Source BFS):

   • Initialize a distance matrix dist of size $N \times N$ with infinity (or -1).
   • Push all coordinates (r, c) containing a thief (grid[r][c] == 1) into a queue and set their dist to 0.
   • Perform BFS. For each cell, update its unvisited neighbors to have dist[neighbor] = dist[current] + 1.

2. Pathfinding (Dijkstra's Algorithm):

   • Initialize a Max-Heap (Priority Queue).
   • Push the starting cell (0, 0) into the heap. The priority value is dist[0][0].
   • Maintain a visited matrix to avoid cycles and redundant processing.
   • While the heap is not empty:
     • Pop the element with the highest safeness factor: (current_safeness, r, c).
     • If (r, c) is the destination (n-1, n-1), return current_safeness.
     • For each valid neighbor (nr, nc):
       • Calculate the new path safeness: new_safe = min(current_safeness, dist[nr][nc]).
       • If (nr, nc) has not been visited, mark it as visited and push (new_safe, nr, nc) to the heap.

Execution Flow

Let's trace the algorithm on a simplified $3 \times 3$ grid.

Input Grid:

0 0 1
0 0 0
0 0 0

Thief at (0, 2).

Step 1: Multi-Source BFS

• Queue starts with [(0, 2)]. dist[0][2] = 0.
• Expand (0, 2): Update neighbors (0, 1) and (1, 2) to distance 1.
• Expand layer 1: Update neighbors (0, 0), (1, 1), (2, 2) to distance 2.
• Expand layer 2: Update neighbors (1, 0), (2, 1) to distance 3.
• Expand layer 3: Update neighbor (2, 0) to distance 4.

Resulting Distance Matrix:

2 1 0
3 2 1
4 3 2

Step 2: Modified Dijkstra

• Init: Max-Heap contains [(2, 0, 0)]. (Value 2 comes from dist[0][0]). Visited (0, 0).
• Pop: (2, 0, 0). Neighbors: (0, 1) [dist 1], (1, 0) [dist 3].
  • Push (min(2, 1), 0, 1) $\to$ (1, 0, 1).
  • Push (min(2, 3), 1, 0) $\to$ (2, 1, 0).
  • Heap: [(2, 1, 0), (1, 0, 1)].
• Pop: (2, 1, 0). Neighbors: (2, 0) [dist 4], (1, 1) [dist 2].
  • Push (min(2, 4), 2, 0) $\to$ (2, 2, 0).
  • Push (min(2, 2), 1, 1) $\to$ (2, 1, 1).
  • Heap: [(2, 2, 0), (2, 1, 1), (1, 0, 1)].
• Pop: (2, 2, 0). Neighbors: (2, 1) [dist 3].
  • Push (min(2, 3), 2, 1) $\to$ (2, 2, 1).
  • Heap: [(2, 2, 1), (2, 1, 1), (1, 0, 1)].
• Pop: (2, 2, 1). Neighbors: (2, 2) [dist 2].
  • Push (min(2, 2), 2, 2) $\to$ (2, 2, 2).
  • Heap: [(2, 2, 2), (2, 1, 1), (1, 0, 1)].
• Pop: (2, 2, 2). This is target (n-1, n-1).
• Return: 2.

Proof of Correctness

The correctness relies on the greedy choice property of Dijkstra's algorithm.

1. Distance Field Accuracy: The Multi-Source BFS guarantees that dist[r][c] holds the true minimum Manhattan distance to any thief because BFS finds shortest paths in unweighted graphs layer by layer.
2. Optimal Substructure: The safeness of a path ending at u is determined by min(safeness of path to parent, dist[u]).
3. Greedy Choice: By using a Max-Heap, we always extend the path that currently has the highest bottleneck value. When we first extract the destination node from the priority queue, the value associated with it is guaranteed to be the maximum possible safeness factor. Any other path to the destination would have been extracted later (meaning it has a lower or equal safeness factor) or is an extension of a path with a lower safeness factor.

Reference Implementation

C++ Solution for LeetCode 2812

cpp
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0;

        // Step 1: Multi-source BFS to calculate distance to nearest thief
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int, int>> q;

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 1) {
                    dist[r][c] = 0;
                    q.push({r, c});
                }
            }
        }

        int dr[] = {0, 0, 1, -1};
        int dc[] = {1, -1, 0, 0};

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            for (int i = 0; i < 4; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }

        // Step 2: Dijkstra's Algorithm (Max-Heap) to find max safeness path
        // Priority Queue stores {safeness, r, c}
        priority_queue<tuple<int, int, int>> pq;
        pq.push({dist[0][0], 0, 0});
        
        // Reuse dist array to mark visited nodes by setting to -1 
        // (or use a separate visited array)
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;

        while (!pq.empty()) {
            auto [safe, r, c] = pq.top();
            pq.pop();

            if (r == n - 1 && c == n - 1) return safe;

            for (int i = 0; i < 4; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    // The path safeness is limited by the smallest value seen so far
                    int newSafe = min(safe, dist[nr][nc]);
                    pq.push({newSafe, nr, nc});
                }
            }
        }

        return 0;
    }
};

Java Solution for LeetCode 2812

java
import java.util.*;

class Solution {
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) return 0;

        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        
        Queue<int[]> q = new LinkedList<>();

        // Step 1: Multi-source BFS
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid.get(r).get(c) == 1) {
                    dist[r][c] = 0;
                    q.offer(new int[]{r, c});
                }
            }
        }

        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }

        // Step 2: Dijkstra's Algorithm using Max-Heap
        // Stores int[]{safeness, r, c}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        pq.offer(new int[]{dist[0][0], 0, 0});
        
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int safe = curr[0], r = curr[1], c = curr[2];

            if (r == n - 1 && c == n - 1) return safe;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    int newSafe = Math.min(safe, dist[nr][nc]);
                    pq.offer(new int[]{newSafe, nr, nc});
                }
            }
        }

        return 0;
    }
}

Python Solution for LeetCode 2812

python
import heapq
from collections import deque

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return 0
            
        # Step 1: Multi-source BFS to calculate distances
        dist = [[-1] * n for _ in range(n)]
        q = deque()
        
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    dist[r][c] = 0
                    q.append((r, c))
                    
        dr = [0, 0, 1, -1]
        dc = [1, -1, 0, 0]
        
        while q:
            r, c = q.popleft()
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))
                    
        # Step 2: Dijkstra's Algorithm (Max-Heap)
        # Python's heapq is a min-heap, so we store negative safeness
        pq = [(-dist[0][0], 0, 0)]
        visited = set()
        visited.add((0, 0))
        
        while pq:
            safe, r, c = heapq.heappop(pq)
            safe = -safe # Convert back to positive
            
            if r == n - 1 and c == n - 1:
                return safe
            
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    new_safe = min(safe, dist[nr][nc])
                    heapq.heappush(pq, (-new_safe, nr, nc))
                    
        return 0