286. Walls and Gates - Detailed Explanation

Problem Statement

You are given an m × n grid (2D matrix) where:

• 0 represents a gate.
• INF (2147483647) represents an empty room.
• -1 represents a wall.

The task is to fill each empty room with the distance to its nearest gate. If a room cannot reach any gate, it should remain INF.

Constraints

• (1 \leq m, n \leq 200)
• rooms[i][j] is -1, 0, or INF.

Example

Input

rooms = [
  [INF, -1,  0,  INF],
  [INF, INF, INF, -1],
  [INF, -1, INF, -1],
  [0,   -1, INF, INF]
]

Output

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

Explanation

• Each empty room is filled with the shortest distance to its nearest gate.
• The BFS (Breadth-First Search) traversal ensures minimum distances.

Hints

1. Instead of searching from every empty room, start BFS from all gates (0s) at the same time.
2. Use BFS (level-order traversal) instead of DFS, as BFS guarantees shortest paths in an unweighted grid.
3. Use a queue to process cells efficiently.

Approach 1: Multi-Source BFS (Optimal Solution)

Idea

• Multi-source BFS: Start from all gates (0s) simultaneously and spread outwards.
• Why BFS? BFS ensures the shortest path is found in an unweighted graph.
• Each cell propagates its distance to its unvisited neighbors.

Algorithm

1. Find all gates (0s) and add them to a queue.
2. Start BFS traversal, updating empty rooms (INF) with their shortest distance from a gate.
3. Stop if a cell is already visited (i.e., it has a smaller distance).

Time Complexity

• O(m × n) because each cell is processed once.

Python Implementation

Java Implementation