Given an image represented by a 2D matrix of integers, an initial pixel, and a new color, implement the flood fill algorithm to change all connected pixels with the initial color to the new color.
Each pixel in the image is represented by a positive integer, and the image is represented by an ‘n x m’ matrix, where ‘n’ is the number of rows and ‘m’ is the number of columns.
A pixel is considered connected to its adjacent neighbors to the left, right, top, and bottom, but not diagonally.
Table of Contents
Sample Input:
Image:
[
[1, 1, 1],
[1, 1, 0],
[1, 0, 1]
]
Initial Pixel: (1, 1) (row = 1, column = 1)
New Color: 2
Expected Output:
[
[2, 2, 2],
[2, 2, 0],
[2, 0, 1]
]
In this example, we start at the pixel (1, 1) with the initial color 1. We change its color to 2 and then recursively apply the same process to its adjacent connected pixels (top, bottom, left, right) that have the initial color 1 until all connected pixels with the initial color are changed to the new color 2.
Time and Space Complexity:
The time complexity of the algorithm is O(n * m), where ‘n’ is the number of rows and ‘m’ is the number of columns in the image. In the worst case, we may have to visit all pixels in the image. The space complexity is O(n * m) as well, due to the recursion stack, which can grow to the size of the image in the worst case.
C++ solution:
#include <iostream>
#include <vector>
void floodFillRecursive(std::vector<std::vector<int>>& image, int row, int col, int initialColor, int newColor) {
// Base case: If the current pixel is out of bounds or has a color different from the initial color, return.
if (row < 0 || row >= image.size() || col < 0 || col >= image[0].size() || image[row][col] != initialColor) {
return;
}
// Change the color of the current pixel to the new color.
image[row][col] = newColor;
// Recursively fill the connected pixels (top, bottom, left, right) with the new color.
floodFillRecursive(image, row - 1, col, initialColor, newColor); // Top neighbor
floodFillRecursive(image, row + 1, col, initialColor, newColor); // Bottom neighbor
floodFillRecursive(image, row, col - 1, initialColor, newColor); // Left neighbor
floodFillRecursive(image, row, col + 1, initialColor, newColor); // Right neighbor
}
std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int newColor) {
// Base case: If the new color is the same as the initial color, no need to perform the flood fill.
if (image[sr][sc] == newColor) {
return image;
}
// Perform the recursive flood fill starting from the initial pixel (sr, sc).
floodFillRecursive(image, sr, sc, image[sr][sc], newColor);
return image;
}
int main() {
// Construct the image for the sample input
std::vector<std::vector<int>> image = {
{1, 1, 1},
{1, 1, 0},
{1, 0, 1}
};
// Perform the flood fill on the image starting from the initial pixel (1, 1) with new color 2
std::vector<std::vector<int>> resultImage = floodFill(image, 1, 1, 2);
// Print the result
std::cout << "Flood Fill Result:" << std::endl;
for (const auto& row : resultImage) {
std::cout << "[";
for (int i = 0; i < row.size(); ++i) {
std::cout << row[i];
if (i < row.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
return 0;
}
The floodFill function is the entry point of the algorithm, and it calls the recursive helper function floodFillRecursive to perform the actual flood fill operation. The
floodFillRecursive function takes care of changing the color of the current pixel to the new color and recursively calls itself on the connected neighboring pixels with the same initial color.
In the given example, the function will correctly perform the flood fill on the image starting from the initial pixel (1, 1) and change all connected pixels with the initial color 1 to the new color 2, and the output will be as follows:
Flood Fill Result:
[2, 2, 2]
[2, 2, 0]
[2, 0, 1]