#2812
Find the Safest Path in a Grid
specialist · 905 · lc medium +31 · verified · 48.6% accepted · 1,823 likes · top 35%
Description
A 0-indexed n x n grid grid is given, where grid[r][c] = 1 marks a thief and grid[r][c] = 0 marks an empty cell.
Starting at (0, 0), find a path to (n - 1, n - 1). The safeness factor of a path is the minimum Manhattan distance from any cell in the path to the nearest thief.
Return the maximum safeness factor over all paths from (0, 0) to (n - 1, n - 1).
Adjacent cells share an edge. Manhattan distance between (a, b) and (x, y) equals |a - x| + |b - y|.
Example 1:
Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 0
Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).
Example 2:
Input: grid = [[0,0,1],[0,0,0],[0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.
Example 3:
Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
Output: 2
Explanation: The path depicted in the picture above has a safeness factor of 2 since:
- The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2.
- The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2.
It can be shown that there are no other paths with a higher safeness factor.
Code
1
2
3