The main purpose of the flood fill algorithm is to trace out the bounded area with the same color. In this article, we will learn the working and implementation of the flood fill algorithm.
Takeaways
Flood fill is an algorithm mainly used to determine a bounded area connected to a given node in a multi-dimensional array.
Problem Statement:
You are given a integer matrix mat[][] of size n*n which represents an area where each cell is connected to adjacent cells by an undirected edge, where mat[i][j] represents the color of cell (i,j). also a source cell (x,y) and a target color C is given , you are supposed to replace the color of the region connected to cell (x,y) with color C.
In the above scenario, all cells which are of the same color as cell (4,2) will be colored in the same target color.
Assume that each color is represented by an integer number, then it is just a matrix of integers where each integer represents a particular color, and we need to replace the integer of the target cell (x,y) along with its neighbors which contain the integer number by the integer C.
Example:
Input: mat[][] = {
{1,1,1,1,2,2},
{1,1,1,1,2,2},
{3,3,3,3,2,2},
{4,4,4,4,2,2},
{4,4,4,4,4,4},
{4,4,4,4,4,4}
}
x = 4,y=3,C=5
Output:
1 1 1 1 2 2
1 1 1 1 2 2
3 3 3 3 2 2
5 5 5 5 2 2
5 5 5 5 5 5
5 5 5 5 5 5
Explanation:
In the above example, the source cell is (4,3) where we replaced the colors of all neighbor cells of this cell having color same as this color i.e. 4 with color 5.
How does Flood Fill Algorithm Works?
Let’s build an intuition on how to solve this problem.
First of all, it is given that we can move to left, right, up, and down from the current cell and our target is to change the color of all the connected cells having the color as the color of the source cell to the given color C, since we need to check all the neighbor cells,Breadth-first search quickly comes into the mind where we can start the BFS from the source cell and visit the entire valid region while the motion is only constrained to adjacent four directions.
So in each move (left, right, up, down), we are checking the validity of the new cell by checking whether it has the same color as the source cell had then we replace the color of that cell otherwise we skip that cell, in this way the entire region with the same color is visited and its color is changed to C.
Breadth-first Search Approach:
- Create an empty queue of pairs to store the cells say que.
- Initialize the queue qu with the source cell coordinates i.e. (x,y) and change its color to target color C.
- Iterate until the queue que is not empty and pop the front cell of the queue.
- For each popped cell check for the valid adjacent cells i.e. in four directions (right,left,up,down) if they have the same color then push them into the queue.
- For the valid adjacent cells, also change their color to C.
Let’s see the implementation of the above approach:
#include<bits/stdc++.h>
using namespace std;
//Dimensions of the matrix
const int N = 6,M=6;
// Function to return true if the given cell is valid
bool isValid(int mat[N][M], int x, int y, int currC, int C){
if(x < 0 || x >= N || y < 0 || y >= M || mat[x][y] != currC || mat[x][y] == C)
return false;
return true;
}
// flood Fill Function.
void floodFillAlgorithm(int mat[N][M], int x, int y, int currC, int C){
// create a queue
queue<pair<int,int>>que;
// push the starting pair into the queue
pair<int,int>p(x,y);
que.push(p);
// Iterate while not empty
while(!que.empty()){
// Dequeue the front node.
pair<int,int>currPair = que.front();
que.pop();
// current coordintes
int currX = currPair.first;
int currY = currPair.second;
// check for the upper adjacent cell
if(isValid(mat, currX-1, currY, currC, C)){
mat[currX-1][currY] = C;
p.first = currX-1;
p.second = currY;
que.push(p);
}
// Check for the lower adjacent cell
if(isValid(mat,currX+1,currY,currC, C)){
mat[currX+1][currY] = C;
p.first = currX+1;
p.second = currY;
que.push(p);
}
// Check for the left adjacent cell
if(isValid(mat,currX,currY-1,currC, C)){
mat[currX][currY-1] = C;
p.first = currX;
p.second = currY-1;
que.push(p);
}
// Check for the right adjacent cell
if(isValid(mat,currX,currY+1,currC,C)){
mat[currX][currY+1] = C;
p.first = currX;
p.second = currY+1;
que.push(p);
}
}
}
//Driver program
int main(){
// Given matrix
int mat[N][M] = {
{1,1,1,1,2,2},
{1,1,1,1,2,2},
{3,3,3,3,2,2},
{4,4,4,4,2,2},
{4,4,4,4,4,4},
{4,4,4,4,4,4}
};
// Source cell coordinates
int x=4;
int y = 3;
// New color
int C = 5;
// source cell color
int currC = mat[x][y];
// Call the algorithm
floodFillAlgorithm(mat,x,y,currC,C);
//Print the result matrix
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cout << mat[i][j] << " ";
}
cout << "\n";
}
}
Output:
1 1 1 1 2 2
1 1 1 1 2 2
3 3 3 3 2 2
5 5 5 5 2 2
5 5 5 5 5 5
5 5 5 5 5 5
In the above implementation, we just implemented simple BFS and we painted the given region with single color C, Now let’s jump into the complexity analysis of the above code
Complexity Analysis
Time Complexity: O(N*M), due to traversal of each and every cell of the matrix. Space Complexity: O(N*M)
Since we know that the solution of the problem involves the traversal of the enclosed region, we may also use depth-first search for that.
Depth-first Search Approach:
Since we know that the solution of the problem involves the traversal of the enclosed region, we may also use depth-first search for that.
- First of all replace the color of the source node with C.
- After that, explore all of the 4 adjacent cells recursively and replace their color with C if they are found valid.
- A valid adjacent cell is the one that has the same color as the source cell.
Let’s see the implementation of the above algorithm:
#include<bits/stdc++.h>
using namespace std;
// Dimensions of the matrix:
const int N = 6, M=6;
// Direction vectors
int row[] = {-1,0,1,0};
int col[] = {0,1,0,-1};
//Function to validate the given cell
bool isValid(int mat[][M], int x, int y, int currC, int C){
if(x >= N || x < 0 || y <0 || y >= M || mat[x][y] != currC || mat[x][y] == C)return false;
return true;
}
// Flood fill recursive function
void floodfill(int mat[][M], int x, int y, int currC, int C){
// Target color is same as the replacement
if(currC == C)return;
// Replace the current pixel color with replacement
mat[x][y]=C;
for(int i=0;i<4;i++){
if(isValid(mat,x+row[i],y+col[i],currC, C))
floodFill(mat,x+row[i],y+col[i],currC,C);
}
}
//Driver program
int main(){
// Given matrix
int mat[N][M] = {
{1,1,1,1,2,2},
{1,1,1,1,2,2},
{3,3,3,3,2,2},
{4,4,4,4,2,2},
{4,4,4,4,4,4},
{4,4,4,4,4,4}
};
// Source cell coordinates
int x=4;
int y = 3;
// New color
int C = 5;
// source cell color
int currC = mat[x][y];
// Call the algorithm
floodFill(mat,x,y,currC,C);
//Print the result matrix
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cout << mat[i][j] << " ";
}
cout << "\n";
}
}
Output:
1 1 1 1 2 2
1 1 1 1 2 2
3 3 3 3 2 2
5 5 5 5 2 2
5 5 5 5 5 5
5 5 5 5 5 5
Let’s understand the time and space complexity of the above code:
Complexity Analysis
Let’s understand the time and space complexity of the above code:
- Time complexity = O(N * M), as each cell of the matrix is visited once, performing constant-time operations.
- Space complexity = O(N * M), where N and M are the dimensions of the input matrix.
Conclusion:
- The flood fill algorithm is a versatile technique used for filling connected regions of a grid with a specified color.
- It can be applied in various scenarios such as computer graphics, image processing, and game development.
- Implemented using either Depth-First Search (DFS) or Breadth-First Search (BFS), the algorithm offers an efficient solution with a time complexity of O(N * M) and a space complexity of O(N * M) in the worst case, where N and M are the dimensions of the grid.
- The choice between DFS and BFS depends on factors such as the nature of the grid and the desired order of traversal.
- DFS may be preferred for simplicity and ease of implementation.
- BFS may be more suitable for finding the shortest path or when memory usage is a concern.
- There are uses of flood fill algorithm in computer graphics, image processing, and game development.
