Restaurant Delivery Heatmap
Problem statement
A city map is an n x n grid. Rows and columns are numbered from 0 to n - 1, and cell (x, y) is in row x and column y.
Each restaurant is given as [i, j, r, d]:
- The restaurant is at cell
(i, j). ris its delivery range. It serves every cell(x, y)with|x - i| <= rand|y - j| <= r. These cells form a square of2r + 1rows and2r + 1columns centered on the restaurant, which includes the diagonal directions. Parts of the square that fall outside the grid are ignored.dis the number of deliveries the restaurant is expected to make in each cell it serves.
The heat of a cell is the sum of d over all restaurants that serve it. A cell that no restaurant serves has heat 0.
Return the heatmap: an n x n grid where row x, column y holds the heat of cell (x, y).
Function
deliveryHeatmap(n: int, restaurants: int[][]) → int[][]Examples
Example 1
n = 5restaurants = [[2,3,1,2],[4,4,1,4]]return = [[0,0,0,0,0],[0,0,2,2,2],[0,0,2,2,2],[0,0,2,6,6],[0,0,0,4,4]]The first restaurant sits at row 2, column 3 with range 1, so it adds 2 to rows 1 to 3 and columns 2 to 4. The second sits at row 4, column 4 with range 1. Its square would reach row 5 and column 5, which are outside the grid, so it adds 4 only to rows 3 and 4, columns 3 and 4. Cells (3,3) and (3,4) are covered by both, so they hold 2 + 4 = 6. Row 0 and columns 0 and 1 are not covered by anyone.
Example 2
n = 4restaurants = [[0,0,0,3],[3,0,2,1],[0,0,0,2]]return = [[5,0,0,0],[1,1,1,0],[1,1,1,0],[1,1,1,0]]Two restaurants sit at cell (0,0) with range 0, so each one serves only that cell: it holds 3 + 2 = 5. The restaurant at (3,0) with range 2 would cover rows 1 to 5 and columns -2 to 2. Inside the grid that is rows 1 to 3 and columns 0 to 2, and each of those cells gets 1.
Example 3
n = 3restaurants = [[1,2,10,7],[2,0,1,1]]return = [[7,7,7],[8,8,7],[8,8,7]]The first restaurant has range 10, which is bigger than the grid, so it adds 7 to all 9 cells. The second adds 1 to rows 1 and 2, columns 0 and 1. Those four cells hold 8, and the rest hold 7.
Constraints
1 <= n <= 501 <= restaurants.length <= 2000restaurants[k].length == 4, and each restaurant is[i, j, r, d]0 <= i, j <= n - 10 <= r <= 501 <= d <= 1000