Find the Safest Path in a Grid

The square binary grid marks thieves with 1 and empty cells with 0. A cell's safety is its Manhattan distance to the nearest thief: the distance between (r,c) and (x,y) is |r-x| + |c-y|. Travel from (0,0) to (n-1,n-1) using moves up, down, left, or right. You may visit any cell, including a thief's cell. A path's safeness factor is the smallest cell safety encountered anywhere on that path, including its endpoints. Return the largest possible safeness factor. The grid contains at least one thief.

Filled cells contain thieves; hatching marks one safest route through the grid.

Example 1:

Input: grid = [[0,1],[0,0]]

Output: 1

Explanation: Take (0,0) → (1,0) → (1,1). The distances to the thief at (0,1) are 1, 2, and 1, so this path has safeness 1. No path can exceed 1 because the starting cell has safety 1.

Example 2:

Input: grid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 1

Explanation: Travel along the top and right edges to avoid the center thief. Every visited cell stays at least one step away. Both possible first moves are only one step from the thief, so a safeness factor of 2 is impossible.

Example 3:

Input: grid = [[1]]

Output: 0

Explanation: The start and destination are the same cell, and that cell contains a thief. Its distance to the nearest thief is 0, so the answer is 0.

Constraints:

• 1 <= n <= 400; grid has n rows and n columns.
• Every entry is 0 or 1.
• At least one cell contains 1.