Show problems as
Classic problem #2812MediumArrayBinary SearchBreadth-First SearchUnion-FindHeap (Priority Queue)Matrix

Find the Safest Path in a Grid

Real-world version: Widest Margin Across the Block
Tracked in this browser only
Read Find the Safest Path in a Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A city block is mapped as an n x n array of cells called grid. A cell holding 1 has a hazard standing in it and a cell holding 0 is empty. At least one cell holds a hazard.

A courier begins in the cell at row 0, column 0 and has to finish in the cell at row n - 1, column n - 1. One move takes the courier to a cell that shares an edge with the current cell and lies inside the block. Cells may be entered more than once, and a cell holding a hazard may be entered like any other.

The clearance of a cell is the smallest value of |r - hr| + |c - hc| over every hazard cell (hr, hc), where (r, c) is the cell itself. The margin of a walk is the smallest clearance found among the cells it enters, counting the first cell and the last cell.

Return the largest margin achievable by a walk from row 0, column 0 to row n - 1, column n - 1.

Examples

Example 1

Input
grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output
1

The only hazard sits in the middle cell, whose clearance is 0. Both corners have clearance 2, and the walk down the left column then along the bottom row enters only cells of clearance 1 or more, so its margin is 1.

Example 2

Input
grid = [[1, 0], [0, 0]]
Output
0

The starting cell itself holds the hazard, so its clearance is 0. Every walk begins there, which caps the margin at 0.

Example 3

Input
grid = [[0, 1, 0], [0, 0, 0], [0, 1, 0]]
Output
1

Both corners of interest have clearance 1, and the middle cell of the grid also has clearance 1, so the walk through the middle row keeps a margin of 1.

Constraints

  • 1 <= grid.length == n <= 400
  • grid[i].length == n
  • grid[i][j] is either 0 or 1.
  • At least one cell of the block holds a hazard.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_safeness_factor(grid: list[list[int]]) -> int:
Java
public int maximumSafenessFactor(List<List<Integer>> grid)

More on the same topics