C++ Flood Fill Algorithm














































C++ Flood Fill Algorithm



Flood fill Algorithm  how to implement fill() in paint


In MS-Paint, when we take the brush to a pixel and click, the color of the region of that pixel is replaced with a new selected color. Following is the problem statement to do this task. 
Given a 2D screen, location of a pixel in the screen and a color, replace color of the given pixel and all adjacent same colored pixels with the given color.

Example: 

Input:
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
x = 4, y = 4, newColor = 3
The values in the given 2D screen
indicate colors of the pixels.
x and y are coordinates of the brush,
newColor is the color that
should replace the previous color on
screen[x][y] and all surrounding
pixels with same color.

Output:
Screen should be changed to following.
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1},
};



 

This question can be solved using either Recursion or BFS. Both the solutions are discussed below 
1:- Using Recursion 
The idea is simple, we first replace the color of the current pixel, then recur for 4 surrounding points. The following is a detailed algorithm. 

// A recursive function to replace 
// previous color 'prevC' at '(x, y)'
// and all surrounding pixels of (x, y)
// with new color 'newC' and
floodFil(screen[M][N], x, y, prevC, newC)
1) If x or y is outside the screen, then return.
2) If color of screen[x][y] is not same as prevC, then return
3) Recur for north, south, east and west.
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);


The following is the implementation of the above algorithm.  

// A C++ program to implement flood fill algorithm
#include<iostream>
using namespace std;
// Dimentions of paint screen
#define M 8
#define N 8
// A recursive function to replace previous color 'prevC' at '(x, y)'
// and all surrounding pixels of (x, y) with new color 'newC' and
void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != prevC)
return;
if (screen[x][y] == newC)
return;
// Replace the color at (x, y)
screen[x][y] = newC;
// Recur for north, east, south and west
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
}
// It mainly finds the previous color on (x, y) and
// calls floodFillUtil()
void floodFill(int screen[][N], int x, int y, int newC)
{
int prevC = screen[x][y];
floodFillUtil(screen, x, y, prevC, newC);
}
// Driver code
int main()
{
int screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
int x = 4, y = 4, newC = 3;
floodFill(screen, x, y, newC);
cout << "Updated screen after call to floodFill: \n";
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
}


Output:
Updated screen after call to floodFill: 
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1


Method 2: Using the BFS approach

Algorithm for BFS based approach :

  1. Create a queue of pairs.
  2. Insert an initial index given in the queue.
  3. Mark initial index as visited in vis[][] matrix.
  4. Until the queue is not empty repeat step 3.1 to 3.6
    • Take the front element from the queue
    • Pop from the queue
    • Store current value/colour at coordinate taken out from queue (precolor)
    • Update the value/color of the current index which is taken out from the queue
    • Check for all 4 direction i.e (x+1,y),(x-1,y),(x,y+1),(x,y-1) is valid or not and if valid then check that value at that coordinate should be equal to precolor and value of that coordinate in vis[][] is 0.
    • If all the above condition is true push the corresponding coordinate in queue and mark as 1 in vis[][]
  5. Print the matrix.

Below is the implementation of the above approach:  

// CPP program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check valid coordinate
int validCoord(int x, int y, int n, int m)
{
if (x < 0 || y < 0) {
return 0;
}
if (x >= n || y >= m) {
return 0;
}
return 1;
}
// Function to run bfs
void bfs(int n, int m, int data[][8],
int x, int y, int color)
{
// Visiing array
int vis[101][101];
// Initialing all as zero
memset(vis, 0, sizeof(vis));
// Creating queue for bfs
queue<pair<int, int> > obj;
// Pushing pair of {x, y}
obj.push({ x, y });
// Marking {x, y} as visited
vis[x][y] = 1;
// Untill queue is emppty
while (obj.empty() != 1)
{
// Extrating front pair
pair<int, int> coord = obj.front();
int x = coord.first;
int y = coord.second;
int preColor = data[x][y];
data[x][y] = color;
// Poping front pair of queue
obj.pop();
// For Upside Pixel or Cell
if (validCoord(x + 1, y, n, m)
&& vis[x + 1][y] == 0
&& data[x + 1][y] == preColor)
{
obj.push({ x + 1, y });
vis[x + 1][y] = 1;
}
// For Downside Pixel or Cell
if (validCoord(x - 1, y, n, m)
&& vis[x - 1][y] == 0
&& data[x - 1][y] == preColor)
{
obj.push({ x - 1, y });
vis[x - 1][y] = 1;
}
// For Right side Pixel or Cell
if (validCoord(x, y + 1, n, m)
&& vis[x][y + 1] == 0
&& data[x][y + 1] == preColor)
{
obj.push({ x, y + 1 });
vis[x][y + 1] = 1;
}
// For Left side Pixel or Cell
if (validCoord(x, y - 1, n, m)
&& vis[x][y - 1] == 0
&& data[x][y - 1] == preColor)
{
obj.push({ x, y - 1 });
vis[x][y - 1] = 1;
}
}
// Printing The Changed Matrix Of Pixels
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << data[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
// Driver Code
int main()
{
int n, m, x, y, color;
n = 8;
m = 8;
int data[8][8] = {
{ 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 0, 0 },
{ 1, 0, 0, 1, 1, 0, 1, 1 },
{ 1, 2, 2, 2, 2, 0, 1, 0 },
{ 1, 1, 1, 2, 2, 0, 1, 0 },
{ 1, 1, 1, 2, 2, 2, 2, 0 },
{ 1, 1, 1, 1, 1, 2, 1, 1 },
{ 1, 1, 1, 1, 1, 2, 2, 1 },
};
x = 4, y = 4, color = 3;
// Function Call
bfs(n, m, data, x, y, color);
return 0;
}
Output
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1



More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 0
C++ Gold Mine Problem 294 0
C++ Merge K Sorted Arrays 116 0
C++ K Centers Problem 239 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 285 0
C++ Find Non Repeating Elements in Array 86 0
C++ Merge Two Binary Trees 120 0
C++ Sum of Numbers From Root To Leaf Paths 88 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 199 0
C++ Smallest window with all characters in string 93 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 86 0
C++ Minimum characters added at front of string in palindrome conversion 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 75 0
C++ Anagram substring Search 71 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 0
C++ Basics of String Manipulation 84 1
C++ Disjoint Data Structure Cycle Detection 86 0
C++ Problem On Disjoint Data Structures 94 0
C++ Disjoint Data Structures Part3 78 0
Disjoint Data Structures Part2 90 0
Disjoint Data Structures 92 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 278 1
C++ Greedy Approach Minimum number of coins 525 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 246 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 457 1
C++ Greedy Approach N-array maximum sum 333 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 545 1
C++ Greedy Approach Minimum Product Subset 348 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 744 1
C++ Greedy Approach-Egyptian Fractions 639 0
C++ Greedy Approach-Huffman Codes 1030 1
C++ Introduction to Greedy Approach 955 2

Comments