Bleeding Ink
Problem statement
A sheet of paper is a grid with height rows and width columns. Every cell starts white, with darkness 0.
You drop ink dots onto the paper. dots[i] = [row, col, darkness] means a dot with that darkness lands on cell (row, col). Rows and columns are numbered from 0.
The ink then bleeds:
- It spreads to the cells above, below, left and right of a cell, never diagonally. It never leaves the paper.
- Each cell it moves into lowers its darkness by
1. Once the ink reaches darkness0, it stops spreading. - So a dot dropped at
(dot_row, dot_col)can give cell(row, col)the darknessdot_darkness - abs(dot_row - row) - abs(dot_col - col). - When several dots reach the same cell, or several dots land on the same cell, the cell keeps the highest value. A cell that no ink reaches stays at
0.
After every dot has finished bleeding, return the total darkness of the paper: the sum of the darkness of all its cells.
Function
totalDarkness(height: int, width: int, dots: int[][]) → intExamples
Example 1
height = 3width = 4dots = [[0,0,255],[1,2,255]]return = 3046Both dots have darkness 255. Each cell keeps the higher of 255 - distance to the two dots:
| cell | col 0 | col 1 | col 2 | col 3 |
|---|---|---|---|---|
| row 0 | 255 | 254 | 254 | 253 |
| row 1 | 254 | 254 | 255 | 254 |
| row 2 | 253 | 253 | 254 | 253 |
For example, cell (0, 2) is 2 steps from the first dot (253) and 1 step from the second (254), so it keeps 254. The rows add up to 1016 + 1017 + 1013 = 3046.
Example 2
height = 5width = 6dots = [[1,0,10],[2,2,9],[2,3,5],[4,2,9]]return = 217After bleeding, the paper looks like this:
| cell | col 0 | col 1 | col 2 | col 3 | col 4 | col 5 |
|---|---|---|---|---|---|---|
| row 0 | 9 | 8 | 7 | 6 | 5 | 4 |
| row 1 | 10 | 9 | 8 | 7 | 6 | 5 |
| row 2 | 9 | 8 | 9 | 8 | 7 | 6 |
| row 3 | 8 | 7 | 8 | 7 | 6 | 5 |
| row 4 | 7 | 8 | 9 | 8 | 7 | 6 |
The dot [2,3,5] adds nothing: the dot [2,2,9] is one step away and already gives that cell 8, which is more than 5. The rows add up to 39 + 45 + 47 + 41 + 45 = 217.
Example 3
height = 2width = 3dots = [[0,1,3],[0,1,1],[1,2,2]]return = 12Two dots land on cell (0, 1). It keeps the darker one, 3, even though the dot with darkness 1 comes later. The paper ends up as:
| cell | col 0 | col 1 | col 2 |
|---|---|---|---|
| row 0 | 2 | 3 | 2 |
| row 1 | 1 | 2 | 2 |
Cell (1, 2) gets 2 from its own dot (the first dot would give it only 1). The total is 7 + 5 = 12.
Constraints
1 <= height <= 5001 <= width <= 5001 <= dots.length <= 10^4dots[i].length == 30 <= dots[i][0] < height0 <= dots[i][1] < width0 <= dots[i][2] <= 255