Flood Fill with BFS or DFS

Problem

Given an image grid, a starting pixel (sr, sc) and a new colour, return a copy of the image with the four-directionally connected region of the original colour recoloured.

If the starting colour already equals the new colour, return the image unchanged to avoid infinite spreading. Use BFS or DFS.

Hint

Mark cells with the new colour when enqueueing so they are never visited twice.

Test cases

case 1

in: [[[1,1,1],[1,1,0],[1,0,1]],1,1,2]

expected: [[2,2,2],[2,2,0],[2,0,1]]

case 2

in: [[[0,0,0],[0,0,0]],0,0,0]

expected: [[0,0,0],[0,0,0]]

case 3

in: [[[0,0,0],[0,1,1]],1,1,1]

expected: [[0,0,0],[0,1,1]]

case 4

in: [[[5]],0,0,3]

expected: [[3]]

case 5

in: [[[1]],0,0,1]

expected: [[1]]

Starter codePython

def flood_fill(image, sr, sc, color):
    # Your code here
    pass

5 test cases · run your code against them in the editor