Walls and Gates

Given a room grid where -1 is a wall, 0 is a gate, and INF represents an empty room, fill each empty room with the distance to its nearest gate. Pattern focus: Grid Graph Traversal. Run multi-source BFS from every gate simultaneously.

Input Format

rooms = 2D integer matrix

Output Format

matrix of minimum distances to nearest gate

Constraints

• 1 <= rows * cols <= 10^5
• rooms contains -1, 0, or INF.

Examples

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

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

rooms = [[0]]

[[0]]

rooms = [[-1]]

[[-1]]