Solution: Flood Fill

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 $(4 \times 4)$ grid has a source value of $1$ at coordinates $[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 \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: