We all are known to the “Bucket” tool of Microsoft Paint which is used to fill an area with single specific color. But do we know how it actually works? Well, Let’s discuss this. Yeah you read it right. We are going to discuss the algorithm behind the bucket tool. And this particular algorithm is known as . Flood Fill Algorithm Problem Description: A two dimensional array will be given with all the different color values in it. The starting point and the new color value will also be given. All we need to do is to fill the section with the new color where the bucket tool is clicked. We can consider the following image as an example. We can represent the above images with two dimensional arrays. Here the Green color is represented with the value 1, Red color with the value 2, Yellow color with the value 3 and Orange color with the value 4 in it. Now we have to take the bucket tool and select a new color and if we click on the red section, it will be colored with the new selected color. Let the new color is Blue and its value is 5. How to solve: We need to find the pixels with red color values, means the indexes with the value 2 and then replace them with the new color. We will solve this problem using a . Recursive Function A function that calls itself during execution is known as Recursive Function. If we have clear concept on or , then the problem is very easy to solve. Recursion Recursive Function Let, the image matrix as image[row][col] and the starting position is (2,4). So, we will start checking from the position image[2][4]. The idea is simple. At first we replace the color of current pixel and then we will go in 8 directions(N, S, W, E, NW, NE, SW, SE) and convert all the previous color values into the new color values. floodFill(image[row][col], x, y, prevColor, newColor) If x y is outside the image, then . If image[x][y] is same as previous color value, then . Call the function north, south, east, west, north-west, north-east, south-west, south-east. FloodFill(image, x+ , y, prevColor, newColor); FloodFill(image, x, y+ , prevColor, newColor); FloodFill(image, x , y, prevColor, newColor); FloodFill(image, x, y , prevColor, newColor); FloodFill(image, x+ , y+ , prevColor, newColor); FloodFill(image, x+ , y , prevColor, newColor); FloodFill(image, x , y+ , prevColor, newColor); FloodFill(image, x , y , prevColor, newColor); //Pseudo code of the recursive function 1. or return 2. not return 3. for 1 1 -1 -1 1 1 1 -1 -1 1 -1 -1 Then we will get the image with new color. Implemention : The following is the implementation of above . algorithm ; image[ ][ ]; row,col; { (i< || i>=row || j< || j>=col) ; ; } { (valid(x,y) == ) ; (image[x][y] != prevColor) ; (image[x][y] == newColor) ; (image[x][y] == prevColor) image[x][y] = newColor; floodFill(x ,y,prevColor,newColor); floodFill(x+ ,y,prevColor,newColor); floodFill(x,y ,prevColor,newColor); floodFill(x,y+ ,prevColor,newColor); floodFill(x ,y ,prevColor,newColor); floodFill(x ,y+ ,prevColor,newColor); floodFill(x+ ,y ,prevColor,newColor); floodFill(x+ ,y+ ,prevColor,newColor); } { x, y, prevColor, newColor; << ; >>row>>col; << << ; ( i= ;i<row;i++) { ( j= ;j<col;j++) { >>image[i][j]; } } << ; >>x>>y; << ; >>newColor; prevColor = image[x ][y ]; floodFill(x,y,prevColor,newColor); ( i= ;i<row;i++) { ( j= ;j<col;j++) { <<image[i][j]<< ; } << ; } ; } # include <bits/stdc++.h> using namespace std # ll long long define int 1000 1000 int bool valid ( i, j) int int if 0 0 return false else return true void floodFill ( x, y, prevColor, newColor) int int int int if false //Base Case return if return if return if //Converting the previous color into new color -1 1 -1 1 -1 -1 -1 1 1 -1 1 1 int main () int cout "Enter row and column number for the image matrix : " cin cout "Enter the image matrix : " endl for int 0 for int 0 cin cout "Enter the starting position : " cin cout "Enter the new color value : " cin -1 -1 for int 0 for int 0 cout " " cout endl return 0 Again we can be asked for calculating the number of pixels each color covers. We can solve this problem simply using the . Implementation of this problem is here. Flood Fill Algorithm ; cnt = , row, col; image[ ][ ]; visited[ ][ ]; res[ ]; { (i< || i>=r || j< || j>=c) ; ; } { (valid(i,j) == ) ; (image[i][j] != idxValue) ; (image[i][j] == idxValue) cnt++; visited[i][j] = ; image[i][j] = ; floodFill(i ,j,idxValue); floodFill(i+ ,j,idxValue); floodFill(i,j ,idxValue); floodFill(i,j+ ,idxValue); floodFill(i ,j ,idxValue); floodFill(i ,j+ ,idxValue); floodFill(i+ ,j ,idxValue); floodFill(i+ ,j+ ,idxValue); } { (visited, , visited); >>row>>col; < > st; < > :: iterator it; ( i= ;i<row;i++) { ( j= ;j<col;j++) { >>image[i][j]; } } ( i= ;i<row;i++) { ( j= ;j<col;j++) { (visited[i][j]== && image[i][j]>= ) { cnt = ; x = image[i][j]; floodFill(i,j,image[i][j]); retCount = cnt; res[x] += retCount; } } } ( i= ;i< ;i++) { (res[i]> ) << <<i<< <<res[i]<< << ; } ; } # include <bits/stdc++.h> using namespace std # ll long long define int 0 int 1000 1000 bool 1000 1000 int 1000 bool valid ( i, j) int int if 0 0 return false else return true void floodFill ( i, j, idxValue) int int int if false //Base case return if return if 1 //Current node is marked as visited. -100 -1 1 -1 1 -1 -1 -1 1 1 -1 1 1 int main () memset 0 sizeof cin set int set int for int 0 for int 0 cin for int 0 for int 0 if 0 0 0 int int //Storing the pixel counts. for int 0 1000 if 0 cout "The color with value " " covers " " pixels." endl return 0 Input : 5 7 1 1 1 1 2 2 2 1 1 1 1 2 2 2 1 1 1 1 2 2 2 1 1 1 1 3 3 3 1 1 1 1 3 3 3 Output : The color with value 1 covers 20 pixels. The color with value 2 covers 9 pixels. The color with value 3 covers 6 pixels. This is all about Flood Fill Algorithm. For any type of confusion I would request you to ask questions in comment section. Stay Home. Stay Safe. Happy Coding!
