Walls and Nearest Gate for Empty Rooms
You are given a rectangular grid containing walls, gates, and empty rooms. Fill every reachable empty room with the minimum number of steps required to reach a gate.
Grid Representation
-1 represents a wall or obstacle.0 represents a gate.2,147,483,647 represents an empty room and is treated as infinity.
The grid is provided as a List<String>. Each string represents one row, and its integer values are separated by commas.
Movement is allowed only between vertically or horizontally adjacent cells. Walls cannot be crossed, and diagonal movement is not allowed.
For every empty room, replace 2,147,483,647 with the distance to its nearest reachable gate. If no gate can be reached, leave the value as 2,147,483,647.
Method
Fill Room Distances
List<String> wallsAndGates(List<String> rooms)
rooms contains the rows of the grid.- Each row contains the same number of comma-separated integers.
- Return the completed grid using the same
List<String> format.
- The order of rows and cells must remain unchanged.
Distance Rules
- A move to an adjacent cell has a distance of
1.
- Only upward, downward, left, and right movement is allowed.
- A gate always remains
0.
- A wall always remains
-1.
- If multiple gates are reachable, use the smallest distance.
- An unreachable empty room remains
2,147,483,647.
Constraints
1 ≤ rooms.size() ≤ 2501 ≤ number of values in each row ≤ 250- Every row contains the same number of values.
- Each grid value is one of
-1, 0, or 2,147,483,647.
- The distance from any reachable empty room to its nearest gate is less than
2,147,483,647.
rooms is never empty.
Examples
Example 1
Method call:
wallsAndGates(rooms = List.of( "2147483647,-1,0,2147483647", "2147483647,2147483647,2147483647,-1", "0,-1,2147483647,2147483647" ))
Output:
List.of( "2,-1,0,1", "1,2,1,-1", "0,-1,2,3" )
Each reachable empty room contains its shortest distance to either gate.
Example 2
Method call:
wallsAndGates(rooms = List.of( "2147483647,-1,2147483647", "-1,2147483647,2147483647" ))
Output:
List.of( "2147483647,-1,2147483647", "-1,2147483647,2147483647" )
The grid contains no gate, so every empty room remains unchanged.
Example 3
Method call:
wallsAndGates(rooms = List.of( "2147483647,2147483647,2147483647", "2147483647,0,-1", "2147483647,2147483647,2147483647" ))
Output:
List.of( "2,1,2", "1,0,-1", "2,1,2" )
Distances are calculated using only vertical and horizontal movement, while the wall remains unchanged.