Beacon Territories
Medium · graph traversal
A valley is a rectangular grid of cells. Each cell of grid holds one number:
-1is a wall of rock. Nobody can walk through it.0is open ground.- A positive number is a beacon standing on open ground. Every beacon has its own id, and no id appears twice.
A walker moves one step at a time to a neighbouring cell (up, down, left or right) that is not rock, and may walk over other beacons' cells freely. A beacon claims an open cell if it is strictly closer, in steps, than every other beacon.
Return a grid of the same size in which:
- every rock cell is still
-1, - every beacon cell holds its own id,
- every other cell holds the id of the beacon that claims it,
- and a cell that is tied between two or more nearest beacons, or that no beacon can reach, holds
0.
Examples
Example 1
Input: grid = [[1, 0, 0, 0, 2]]
Output: [[1, 1, 0, 2, 2]]
The middle cell is two steps from both beacons, so nobody claims it.
Example 2
Input: grid = [[1, 0, -1, 0, 2]]
Output: [[1, 1, -1, 2, 2]]
The rock splits the row in two, so each beacon claims the open cell on its own side.
Example 3
Input: grid = [[1, -1, 0], [0, -1, 0]]
Output: [[1, -1, 0], [1, -1, 0]]
The right-hand column is cut off from the only beacon by the rock, so it stays 0.
Constraints
- 1 <= rows, cols <= 25
- Every cell is -1, 0 or a beacon id with 1 <= id <= 10000.
- Beacon ids are distinct.
- All rows have the same length.