Problem

You are given an $n \times n$ grid where some cells are dangerous and the rest are safe. A path starts at the top-left cell and ends at the bottom-right cell, moving only in the four cardinal directions and never leaving the grid.

For any cell on a path, define its safeness as the Manhattan distance to the nearest dangerous cell. The safeness factor of a path is the minimum safeness among all cells on that path.

Return the largest possible safeness factor among all valid paths from $(0,0)$ to $(n-1,n-1)$.

Notes

• Dangerous cells are typically marked with 1, and safe cells with 0.
• The Manhattan distance between two cells $(r_1,c_1)$ and $(r_2,c_2)$ is $|r_1-r_2| + |c_1-c_2|$.
• If a path can avoid dangerous cells entirely, its safeness factor may be greater than 0.