Frontend School

Safe Passage Through Minefield

DSA
medium

Safe Passage Through Minefield

Medium
Graph
BFS
DFS
Grid
Pathfinding

Overview

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.

What you need to do / Task

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.

Input & output

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:

  • The length of the shortest path (number of moves) from start to end following the safety rules. If no such path exists, return -1.

Clarifications

  • The robot moves one cell at a time, horizontally or vertically.
  • The path length is the number of moves made from the start cell to the end cell.
  • Both the start and end cells must satisfy the safety condition to be considered valid for traversal.
  • The grid cells (r, c) are 0-indexed.

Examples

1

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).

2

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.

3

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

Constraints & assumptions

  • 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.

What interviewers evaluate

  • Correct application of graph traversal algorithms (BFS/DFS) for shortest path.
  • Accurate implementation of the complex 'safe cell' condition.
  • Robust handling of edge cases, including unreachable paths or invalid start/end points.
  • Efficiency of the solution in terms of time and space complexity.

Loading editor...