Problem Statement

You are given a grid of size m x n filled with three possible values:

• -1 representing a wall or an obstacle.
• 0 representing a gate.
• 2147483647 (INF) representing an empty room.

Fill each empty room with the distance to its nearest gate. If an empty room cannot reach any gate, it should remain 2147483647.

Examples

Example 1

• Input:

  [[2147483647, -1, 0],
   [2147483647, 2147483647, 2147483647],
   [2147483647, -1, 2147483647]]
  

• Expected Output:

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

• Justification:
  • Starting from the gates, calculate the minimum distance for each empty room. Each room contains the minimum steps to the nearest gate.

Example 2

• Input:

  [[0, 2147483647, 2147483647, 0],
   [2147483647, -1, 2147483647, 2147483647],
   [2147483647, -1, -1, 2147483647],
   [0, 2147483647, 2147483647, 0]]
  

• Expected Output:

  [[0, 1, 1, 0],
   [1, -1, 2, 1],
   [1, -1, -1, 1],
   [0, 1, 1, 0]]
  

• Justification:
  • The gates at the corners spread their distances to the empty rooms.

Example 3

• Input:

  [[2147483647, -1, 0, 2147483647],
   [-1, 2147483647, 2147483647, -1],
   [0, -1, 2147483647, 2147483647],
   [2147483647, -1, 2147483647, -1]]
  

• Expected Output:

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

• Justification:
  • The gates in the middle of the grid spread their distances, and the walls prevent certain paths.

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 2³¹ - 1.

Try it yourself

Try solving this question here: