All problems

Paint Bucket Fill

Easy · graph traversal

A small picture is stored as a rectangular grid of whole numbers, where each number is the colour of one pixel. You are using a paint bucket tool. You click on the pixel in row row and column col, and the tool recolours that pixel and its whole region with the colour color.

The region of the clicked pixel is every pixel you can reach from it by moving up, down, left or right one pixel at a time while only stepping on pixels that currently have the same colour as the clicked pixel had before the fill. Pixels that touch the region only at a corner are not part of it. Pixels of any other colour are left alone, even if they sit inside the region.

Return the picture after the fill. If color is already the colour of the clicked pixel, nothing changes. Only the returned picture is checked, so you may change image while you work.

Examples

Example 1

Input: image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]], row = 1, col = 1, color = 2

Output: [[2, 2, 2], [2, 2, 0], [2, 0, 1]]

The clicked pixel has colour 1. Six pixels of colour 1 are connected to it, so they all become 2. The 1 in the bottom right corner only touches the region diagonally, so it stays.

Example 2

Input: image = [[0, 0, 0], [0, 0, 0]], row = 0, col = 0, color = 0

Output: [[0, 0, 0], [0, 0, 0]]

The new colour equals the old one, so the picture does not change.

Example 3

Input: image = [[3, 5, 3], [5, 3, 5]], row = 0, col = 0, color = 9

Output: [[9, 5, 3], [5, 3, 5]]

Both neighbours of the clicked pixel have a different colour, so the region is a single pixel.

Constraints