2812. Find the Safest Path in a Grid

Practice Find the Safest Path in a Grid for free on NudgeCode: Medium, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

grid is an n x n matrix where 1 marks a thief and 0 an empty cell. You walk from (0, 0) to (n-1, n-1), moving up, down, left or right (you may step on any cell, thieves included).

The safeness factor of a path is the smallest Manhattan distance from any cell on the path to any thief. Return the largest safeness factor over all paths.

Example

grid = [[0,0,1],
        [0,0,0],
        [0,0,0]]  ->  2

(Go down the left column and along the bottom row; every cell is at least 2 away from the thief.)

Constraints