Graphs Grids as graphs
434. Flood Fill
You are given an image as a grid of integers, image. image[i][j] is the color of the pixel in row i,
column j. You are also given a starting pixel, at row sr and column sc, and a new color, color.
Paint the region of the starting pixel with color, and return the image. The region is the starting
pixel and every pixel you can reach from it by stepping up, down, left or right, one pixel at a time,
through pixels that have the starting pixel's color. Diagonal steps do not count. Every pixel outside the
region keeps its color.
You may change image itself. Return the image after painting.
Example 1
Input: image = [[1, 1, 0, 2],
[0, 1, 0, 1],
[1, 1, 1, 0]]
sr = 0
sc = 0
color = 5
[[5,5,0,2],[0,5,0,1],[5,5,5,0]]Explanation: Six 1s are joined to the top-left pixel by steps up, down, left and right, and they all become 5. The 1 at row 1, column 3 touches the region only at a corner, so it stays 1.
Example 2
Input: image = [[3, 3], [3, 7]], sr = 1, sc = 0, color = 3
[[3,3],[3,7]]Explanation: The region already has the color 3, so nothing changes.
Example 3
Input: image = [[0, 0, 0], [0, 9, 0]]
sr = 1
sc = 1
color = 0
[[0,0,0],[0,0,0]]Explanation: No neighbour of the starting pixel has the color 9, so the region is that one pixel. It becomes 0, the same color as its neighbours.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == image.length,n == image[i].length1 ≤ m, n ≤ 3000 ≤ image[i][j], color ≤ 1090 ≤ sr < m,0 ≤ sc < n
Clarifying questions
What you would ask an interviewer before writing any code.