All problems

Safest Gallery Walk

Hard · graph traversal

A museum gallery is a grid of rooms. In grid, a 1 is a room with a guard in it and a 0 is an empty room. A visitor enters at the top-left room and leaves at the bottom-right room, and each step moves to a room directly above, below, left or right. Visitors may walk through rooms with guards in them.

The safety of a walk is the smallest distance from any room on the walk (including the first and the last) to any guard. The distance between two rooms is the number of rows apart plus the number of columns apart.

Return the greatest safety that any walk from the top-left room to the bottom-right room can have. The grid always contains at least one guard.

Examples

Example 1

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

Output: 1

Every walk has to pass through one of the four rooms next to the guard, which are at distance 1.

Example 2

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

Output: 2

Every walk has to cross the line of rooms between the two guards, and the best crossing rooms are still 2 away from a guard.

Example 3

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

Output: 0

The guard stands in the last room, so every walk ends at distance 0.

Constraints