Find the Safest Path in a Grid

You are given an n x n binary matrix grid. A cell containing 1 contains a thief, and a cell containing 0 is empty.
Start at (0, 0) and move to (n - 1, n - 1). Each move goes one cell up, down, left, or right, and a path may pass through a thief cell.
The safeness factor of a path is the minimum Manhattan distance from any cell on that path to any thief in the grid. Return the maximum safeness factor among all paths from the start to the destination.
The Manhattan distance between (r, c) and (x, y) is |r - x| + |c - y|.

Function
maximumSafenessFactor(grid: int[][]) → int

Examples
Example 1
grid = [[1,0,0],[0,0,0],[0,0,1]]
return = 0
The start and destination both contain thieves, so every path has safeness factor 0.
Example 2
grid = [[0,0,1],[0,0,0],[0,0,0]]
return = 2
A path through the left and bottom area stays at least Manhattan distance 2 from the thief at (0, 2), and no path can do better.
Example 3
grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
return = 2
A route through the central corridor remains at least distance 2 from both corner thieves.

Constraints
1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] is 0 or 1.
The grid contains at least one thief.

Phase one: run a multi-source BFS from every thief cell at once to fill a dist grid with the Manhattan distance to the nearest thief. Phase two: find the path from (0,0) to (n-1,n-1) that maximizes the minimum dist along it. Two clean ways. Binary search a threshold t and BFS only through cells with dist >= t, or use a max-heap Dijkstra variant where you pop the cell with the best bottleneck so far. Both fit n = 400. Common pitfalls: running a separate BFS per thief (far too slow), forgetting that if the start or end cell has dist 0 the answer is 0, and treating thief cells as walls when they're just low-score cells. Because BFS on a grid gives Manhattan distance with four-direction moves, you don't need a formula per pair. If you freeze on the bottleneck step, StealthCoder is the hedge during the live OA.

The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.