cswork / libraryOpen practice workspace

Coding questions · Meta

Fill rooms with nearest gate distances

This question evaluates grid-based graph traversal and algorithmic problem-solving skills, including concepts such as multi-source breadth-first search, handling sentinel values, and performing in-place updates.

You are given an m×n integer grid representing rooms, where -1 is a wall, 0 is a gate, and INF (a large sentinel such as 2^31−

  1. is an empty room. For each empty room, fill it with the minimum number of steps to the nearest gate using four-directional movement; if unreachable, leave it as INF. Implement an in-place algorithm, justify your traversal strategy (e.g., multi-source BFS), and analyze time and space complexity. Cover edge cases such as multiple gates, enclosed areas, and very large grids.

Fill Rooms with Nearest Gate Distances

Examples

Example 1

Input: ([[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]],)
Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Explanation: Classic walls and gates.

Example 2

Input: ([],)
Output: []

Explanation: Empty grid.

Hints

  1. Model object-style prompts as arrays or operation streams when needed.
  2. Handle empty and boundary cases before the main logic.