Safest Route From Hazards
MediumGraphs ยท Google
Given grid, where 0 is an open cell and 1 is a wall, return the greatest safety of any route from start to goal, or -1 if goal cannot be reached. A route moves up, down, left or right between open cells. Cells are [row, col].
The safety of a route is the smallest Manhattan distance from any cell on it, start and goal included, to its nearest cell in hazards. Distances ignore walls.
Example 1
- Input:
- grid = [[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0]], start = [0, 0], goal = [4, 4], hazards = [[2, 2]]
- Output:
- 2
- Explanation
- The best route keeps at least 2 away from the hazard at
[2, 2]; no route does better.
Example 2
- Input:
- grid = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]], start = [0, 0], goal = [0, 4], hazards = [[1, 2]]
- Output:
- 2
Example 3
- Input:
- grid = [[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]], start = [0, 0], goal = [0, 4], hazards = [[2, 4]]
- Output:
- -1
Constraints
1 <= grid.length, grid[0].length <= 200grid[i][j]is0or1startandgoalare open cells and may be the same cell1 <= hazards.length <= 1000, and every hazard is an open cell; a hazard may bestartorgoal