Safe Passage Through Minefield
In the realm of autonomous navigation systems, especially for hazardous environments like disaster zones or extraterrestrial explorations, ensuring the safety of a robotic agent is paramount. This problem simulates a critical component of such a system: finding the safest possible route through a grid-based environment that may contain hidden dangers.
Your task is to implement a function shortestSafePath that finds the length of the shortest path for a robot to travel from a given start cell to an end cell in a grid. The robot can move horizontally or vertically (4-directional movement). A cell (r, c) is considered safe to enter only if grid[r][c] itself is not a mine, AND none of its 8 surrounding cells (including diagonals) are mines. If any cell within the 3x3 square centered at (r,c) (including (r,c) itself) contains a mine, then (r,c) is not safe to enter.
If the start cell or end cell itself is not safe to enter, or if no path exists, return -1.
Function Signature:
function shortestSafePath(grid: number[][], start: [number, number], end: [number, number]): number
Parameters:
grid: A 2D array (number[][]) representing the minefield. Each cell grid[r][c] contains 0 if it's a safe spot, and 1 if it's a mine.start: An array [row, col] representing the starting coordinates of the robot.end: An array [row, col] representing the target coordinates for the robot.Return Value:
start to end following the safety rules. If no such path exists, return -1.start cell to the end cell.start and end cells must satisfy the safety condition to be considered valid for traversal.(r, c) are 0-indexed.Examples
Example 1
Input:
grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]], start = [0,0], end = [3,3]
Output:
6
Note:
All cells are safe to traverse. A shortest path from (0,0) to (3,3) requires 6 moves (e.g., three moves right, three moves down).
Example 2
Input:
grid = [[0,0,0,0,0],[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0]], start = [0,0], end = [4,4]
Output:
8
Note:
The mine at (2,2) makes a 3x3 region around it impassable (cells (1,1) to (3,3)). A shortest path can go around this blocked region, for example, via (0,4) then (4,4), or (4,0) then (4,4), both requiring 8 moves.
Example 3
Input:
grid = [[0,0,0],[0,1,0],[0,0,0]], start = [0,0], end = [2,2]
Output:
-1
Note:
The mine at (1,1) makes all cells in the 3x3 grid (the entire map) impassable according to the safety rule. This includes the start and end points, so no path exists.
Constraints
1 <= rows, cols <= 200 (where rows is grid.length, cols is grid[0].length)grid[r][c] is either 0 or 1.start and end coordinates are always within the grid boundaries.Loading editor...