def flood_fill(grid, sr, sc, target):
    # If the source cell already has the same value as `target`, return the original grid.
    # We don't need to iterate through the whole grid in this case.
    if grid[sr][sc] == target:
        return grid
    else:
        # Storing the original value of the starting cell in `old_target`,
        # this will help in matching the values of the neighboring cells
        old_target = grid[sr][sc]
        # Replacing the value of the starting cell with the specified target
        grid[sr][sc] = target
        # Calling the DFS() function on the starting cell to replace the values of all connected cells
        dfs(grid, sr, sc, old_target, target)

        # Return the modified grid
        return grid


def dfs(grid, row, col, old_target, new_target):
    # Defining a list of lists that represents the four cells adjacent to the starting cell
    # i).   [0, 1] -> move right 
    # ii).  [1, 0] -> move down
    # iii). [-1, 0] -> move up
    # iv).  [0, -1] -> move left
    adjacent_cells = [[0, 1], [1, 0], [-1, 0], [0, -1]]

    # Get the length of the grid and the length of each row (number of cells)
    grid_length = len(grid)
    total_cells = len(grid[0])

    # For each cell in the list of adjacent cells
    for cell_value in adjacent_cells:
        # Calculate the row and column indices of the adjacent cells
        i = row + cell_value[0]
        j = col + cell_value[1]

        # If the adjacent cell is within the bounds of the grid and has the same value as the starting cell
        if i < grid_length and i >= 0 and j < total_cells and j >= 0 and grid[i][j] == old_target:
            # Replace the value of the adjacent cell with the specified target
            grid[i][j] = new_target
            # Recursively call the DFS() function on the adjacent cell to repeat the process
            dfs(grid, i, j, old_target, new_target)


# Driver code
def main():
    # Input grid of grids
    grids = [[ # testcase 01
                [1, 1, 0, 1, 0], 
                [0, 0, 0, 0, 1], 
                [0, 0, 0, 1, 1], 
                [1, 1, 1, 1, 0], 
                [1, 0, 0, 0, 0]
            ],
            [   # testcase 02
                [1, 1, 0, 1], 
                [0, 0, 0, 0], 
                [0, 0, 0, 1], 
                [1, 1, 1, 1]
            ],
            [   # testcase 03
                [9, 9, 6, 9], 
                [6, 9, 9, 6], 
                [6, 9, 9, 9], 
                [9, 9, 9, 9]
            ],
            [   # testcase 04
                [1, 1, 0, 1], 
                [0, 1, 0, 0], 
                [0, 1, 1, 0], 
                [1, 0, 1, 1]
            ],
            [   # testcase 05
                [1, 2, 0, 0], 
                [3, 1, 3, 6], 
                [7, 2, 1, 5], 
                [1, 9, 2, 1]
            ]]

    starting_row = [4, 2, 2, 2, 1]
    starting_col = [3, 3, 1, 3, 1]
    new_target = [3, 2, 1, 0, 4]

    for i in range(len(grids)):
        print(i + 1, ".\t Grid before flood fill: ", grids[i], sep = "")
        print("\t Starting row and column are: (" , starting_row[i], ", ", starting_col[i], ")", sep = "")
        print("\t Target value: ", new_target[i], sep = "")
        print("\t After perform flood fill: ", flood_fill(grids[i], starting_row[i], starting_col[i], new_target[i]), sep = "")
        print("-" * 100)


if __name__ == '__main__':
    main()