202. Paint Bucket
A drawing program stores a picture as a grid image, where each cell holds a colour number. The paint bucket tool works like this: you click the cell at row r, column c, and every cell that has the same colour as the clicked cell and can be reached from it by moving up, down, left or right through cells of that same colour is repainted with colour.
Cells that have the same colour but are cut off from the clicked cell (they touch it only diagonally, or only through a different colour) are left alone. Return the grid after the click. If the clicked cell already has the colour colour, nothing changes.
Example 1
- Input:
- image = [[3,3,0,3],[3,0,0,3],[5,3,3,3]]r = 0c = 0colour = 7
- Output:
- [[7,7,0,3],[7,0,0,3],[5,3,3,3]]
- Explanation:
The 3s reachable from the top-left cell are the first row's first two cells and the first column's first two cells, so those four cells become 7. The other 3s are cut off by 0s and 5.
Example 2
- Input:
- image = [[2,2],[2,5]]r = 1c = 0colour = 2
- Output:
- [[2,2],[2,5]]
- Explanation:
The clicked cell is already colour 2, so the picture stays the same.
Example 3
- Input:
- image = [[4]]r = 0c = 0colour = 9
- Output:
- [[9]]
- Explanation:
A single-cell picture is simply repainted.
Constraints
1 ≤ image.length, image[0].length ≤ 50
0 ≤ image[i][j], colour ≤ 65535
0 ≤ r < image.length, 0 ≤ c < image[0].length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m × n)
- Space
- O(m × n)