Safest Mouse Path Away from a Cat
Problem statement
A square grid contains land cells marked 0 and impassable water cells marked 1. A mouse starts at start, wants to reach target, and a cat is located at cat. All three coordinates are land cells.
The mouse may move one cell horizontally or vertically through land. The safety of a path is the minimum Manhattan distance from any cell on that path to the cat. Return the maximum possible safety among all mouse paths from start to target, or -1 when no path exists.
Function
maximumMouseSafety(grid: int[][], start: int[], target: int[], cat: int[]) → intExamples
Example 1
grid = [[0,0,0],[0,0,0],[0,0,0]]start = [0,0]target = [2,2]cat = [0,2]return = 2Following the left and bottom edges keeps every visited cell at Manhattan distance at least 2 from the cat.
Example 2
grid = [[0,1,0],[0,1,0],[0,0,0]]start = [0,0]target = [0,2]cat = [1,2]return = 0The water wall forces every route through the cat cell before reaching the target, so the minimum distance is 0.
Example 3
grid = [[0,1],[1,0]]start = [0,0]target = [1,1]cat = [0,0]return = -1Water separates the two land cells.
Constraints
1 <= grid.length == grid[i].length <= 500.- Every grid value is
0or1. start,target, andcateach contain two in-range coordinates on land.