# Solution: Flood Fill

Let's solve the Flood Fill problem using the Backtracking pattern.

## 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 \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

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 \leq$ `grid.length`

,`grid[i].length`

$\leq 30$ $0 \leq$ `grid[i][j]`

,`target`

$\leq 2^{16}$ $0 \leq$ `sr`

$\lt$ `grid.length`

$0 \leq$ `sc`

$\lt$ `grid[i].length`

## Solution

The idea is to change the value of cells in a grid using the depth-first search (DFS) algorithm. The process begins by checking the value of the starting cell. If it already matches the desired `target`

value, the grid is returned unaltered. However, if the value of the starting cell is different from the `target`

value, then we need to update the value of all four directionally connected cells in the grid as well.

We will start by replacing the value of the starting cell with the `target`

value and then use a DFS algorithm to visit the four adjacent cells with the same value as the starting cell. If they have the same value as the starting cell, their value is updated to the `target`

value. This process is repeated until all connected cells of the starting cell have been visited and their values replaced.

The following illustration shows these steps in detail:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.