Paint Bucket Fill

An image is a list of rows, each row a list of integer colour codes. The paint bucket tool of a drawing program repaints the area you click: the clicked cell, plus every cell of the same colour that can be reached from it by stepping up, down, left or right through cells of that colour. Cells that touch only at a corner are not connected.

Write flood_fill(image, row, col, colour) that returns a new image in which the area containing image[row][col] is painted colour, and every other cell keeps its colour. Do not change image itself: build and return a new list of lists.

Examples

image = [[1, 1, 0],
         [1, 0, 2],
         [1, 1, 1]]
flood_fill(image, 0, 0, 5)   # returns [[5, 5, 0], [5, 0, 2], [5, 5, 5]]
flood_fill(image, 1, 1, 7)   # returns [[1, 1, 0], [1, 7, 2], [1, 1, 1]]
flood_fill(image, 2, 2, 1)   # returns [[1, 1, 0], [1, 0, 2], [1, 1, 1]]

In the second call, the 0 in the middle touches the other 0 only at a corner, so it is repainted alone. In the last call the new colour is the old one, so nothing changes.

Constraints

• The image has 1 to 100 rows and 1 to 100 columns.
• 0 <= row < len(image) and 0 <= col < len(image[0]).

Note

An area can hold thousands of cells. A function that calls itself once per cell would go deeper than Python allows (about 1,000 calls), so keep your own list of cells still to visit instead.