Problem Statement

Given a 2D matrix (image) and a starting cell (x, y), change the color of all connected cells (with the same initial color) to a new color.

Input:

• image[][]: A 2D array representing the image.
• x, y: Starting coordinates from where the fill operation starts.
• newColor: The color to which the connected area will be filled.

Output:

The matrix after the flood fill operation.

Examples

Example 1:

Input: image = [[1, 1, 1], 
                [1, 1, 0], 
                [1, 0, 1]]
       x = 1, y = 1
       newColor = 2

Output: [[2, 2, 2],
         [2, 2, 0],
         [2, 0, 1]]

Explanation:
Here, starting at the cell (1, 1), all connected cells with the same color (1) are filled with the new color 2.

Example 2:

Input: image = [
                [0, 0, 0],
                [0, 1, 1]
               ]
       x = 1, y = 1
       newColor = 3
Output: [
         [0, 0, 0],
         [0, 3, 3]
        ]

Explanation:
Here, starting to the cell (1, 1), all connected cells are filled with the new color 3.

Theory

Concept:

• The algorithm starts from the given cell (x, y) and recursively (or iteratively) explores all 4 directions: up, down, left, and right.
• If a neighboring cell has the same color as the starting cell, it is changed to the new color and the algorithm continues to explore its neighbors.
• The algorithm stops when it reaches boundaries or encounters cells with different colors.

Traversal Methods:

• Depth-First Search (DFS): Recursive approach to explore as far as possible along each path before backtracking.
• Breadth-First Search (BFS): Iterative approach using a queue, where neighbors are explored level by level.

Algorithm Steps (DFS Version)

1. Base Case: If the cell (x, y) is outside the grid bounds or has a different color from the starting color, stop the recursion.
2. Change the Color: Update the color of the cell to the new color.
3. Recursive Calls: Recursively apply the flood fill to the 4 neighbors (up, down, left, right).
4. Termination: Continue filling until all connected cells with the same original color are filled with the new color.

Code:

#include <iostream>
#include <vector>

using namespace std;

// Helper function for the DFS-based flood fill
void dfs(vector<vector<int>>& image, int x, int y, int oldColor, int newColor) {
    // Check boundaries and whether the current cell has the original color
    if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != oldColor)
        return;

    // Change the color
    image[x][y] = newColor;

    // Recursive calls for 4-connected neighbors (up, down, left, right)
    dfs(image, x - 1, y, oldColor, newColor); // Up
    dfs(image, x + 1, y, oldColor, newColor); // Down
    dfs(image, x, y - 1, oldColor, newColor); // Left
    dfs(image, x, y + 1, oldColor, newColor); // Right
}

// Main function to apply the flood fill algorithm
vector<vector<int>> floodFill(vector<vector<int>>& image, int x, int y, int newColor) {
    int oldColor = image[x][y];
    
    // If the new color is the same as the original, no need to do anything
    if (oldColor == newColor)
        return image;
    
    // Call DFS to perform the flood fill
    dfs(image, x, y, oldColor, newColor);
    return image;
}

int main() {
    // Example image represented as a 2D grid
    vector<vector<int>> image = {
        {1, 3, 1, 1, 1, 1},
        {1, 1, 0, 1, 1, 1},
        {1, 0, 1, 1, 1, 1}
    };

    int x = 1, y = 1, newColor = 2;

    // Apply flood fill and print the result
    image = floodFill(image, x, y, newColor);

    for (const auto& row : image) {
        for (int pixel : row) {
            cout << pixel << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(M*N)
  • In the worst case, the algorithm visits every cell of the grid exactly once.
  • If the grid has dimensions M*N, the time complexity is: O(M*N).
  • This is because the algorithm may need to fill the entire grid.
• Space Complexity: O(M*N)
  • The space complexity depends on the size of the recursion stack for DFS.
  • In the worst case, the recursion depth could be the size of the grid, which gives a space complexity of: O(M*N).