Steps to the Nearest Exit

Medium

A floor plan is given as a rectangular table plan. Each cell holds one of three values: - -1: a wall; - 0: an exit; - 2147483647: an empty room. In one step you may move to a side-adjacent cell; you cannot pass through walls. Write into every empty room the number of steps to its nearest exit. If no exit can be reached, leave 2147483647 in the room. Return the filled-in plan.

Example 1

plan=[[2147483647, 2147483647, 0], [-1, 2147483647, -1], [2147483647, 2147483647, 2147483647]] → [[2, 1, 0], [-1, 2, -1], [4, 3, 4]]

The answer is [[2, 1, 0], [-1, 2, -1], [4, 3, 4]].

Example 2

plan=[[0, -1, 2147483647]] → [[0, -1, 2147483647]]

The right-hand room is cut off by a wall, so it keeps 2147483647: [[0, -1, 2147483647]].

Constraints

1 ≤ number of rows, number of columns ≤ 250
Every cell is -1, 0 or 2147483647

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium Shortest Path of a Rolling Ball Medium

Input

plan=[[2147483647, 2147483647, 0], [-1, 2147483647, -1], [2147483647, 2147483647, 2147483647]]

Expected

[[2, 1, 0], [-1, 2, -1], [4, 3, 4]]

Run checks the first 3 tests in your browser. Submit checks all 34 tests on the server, hidden ones included.