Flood Fill

Try to solve the Flood Fill problem.

We'll cover the following

Statement#

We are given the following values as input to begin with:

  • The coordinates of a source cell, i.e., sr and sc.

  • A target value, target.

  • An (m×n)(m \times n) grid.

Our task is to perform flood fill by updating the values of the four directionally connected cells, which have the same value as the source cell with the target value.

How to perform flood fill:

Suppose that a (4×4)(4 \times 4) grid has a source value of 11 at coordinates [1,1][1, 1]. We perform flood fill on its neighboring cells only if they have the same source value as this cell. Once all adjacent cells are updated, return the new grid after performing flood fill.

If no neighboring cell has a value equal to the source cell, only update the source cell with the target value and return the updated grid.

Constraints:

  • 1≤1 \leq grid.length, grid[i].length ≤30\leq 30

  • 0≤0 \leq grid[i][j], target ≤216\leq 2^{16}

  • 0≤0 \leq sr <\lt grid.length

  • 0≤0 \leq sc <\lt grid[i].length

Examples#

Created with Fabric.js 3.6.6 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

1 of 3

Created with Fabric.js 3.6.6 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

2 of 3

Created with Fabric.js 3.6.6 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Flood Fill

1

What is the correct output for the following input values?

grid=[1,1,0,1][0,1,1,1][1,0,0,1][1,1,1,1], sr=1, sc=3, target=3grid = \begin{matrix} [1, 1, 0, 1] \\ [0, 1, 1, 1] \\ [1, 0, 0, 1] \\ [1, 1, 1, 1] \end{matrix} ,\space sr = 1,\space sc = 3,\space target = 3

A)

[2,2,0,2][0,2,2,2][2,0,0,2][2,2,2,2] \begin{matrix} [2, 2, 0, 2] \\ [0, 2, 2, 2] \\ [2, 0, 0, 2] \\ [2, 2, 2, 2] \end{matrix}

B)

[3,3,0,3][0,3,3,3][3,0,0,3][3,3,3,3] \begin{matrix} [3, 3, 0, 3] \\ [0, 3, 3, 3] \\ [3, 0, 0, 3] \\ [3, 3, 3, 3] \end{matrix}

C)

[1,1,0,3][0,0,3,3][3,0,0,3][3,3,3,3] \begin{matrix} [1, 1, 0, 3] \\ [0, 0, 3, 3] \\ [3, 0, 0, 3] \\ [3, 3, 3, 3] \end{matrix}

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

For the given source coordinates, check whether the adjacent cells have the same value as this cell.

If any matching coordinate is found, update the value of that cell with the given target value and proceed to the next cell.

Check the adjacent coordinates one by one. If they have the same value as the starting cell, keep updating them by replacing the cell’s values with the target value.

Return the updated grid after replacing the values of the cells that match the source cell’s value.

Try it yourself#

Implement your solution in the following coding playground:

Python
usercode > main.py
Input #1
Input #2
Input #3
Input #4
Flood Fill

Backtracking: Introduction

Solution: Flood Fill