Trusted answers to developer questions

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The **flood fill algorithm** is used to determine the properties of the area around a particular cell in a block. The algorithm is implemented in the bucket fill tool of the *Microsoft Paint* program, which colors the similarly colored pixels, or cells, with another color.

The algorithm is also used in the famous *Minesweeper* game to identify cleared pieces.

The algorithm needs the following data to proceed: the x and y coordinates of the target cell, its current color, and the desired color. It proceeds as follows:

- If $x$ or $y$ is outside the screen, then return.
- If color of screen[$x$][$y$] is not same as current color, then return
- Call recursively for north($x$, $y$+1), south($x$, $y$-1), east($x$+1, $y$) and west($x$-1,$y$).

The code below implements the algorithm mentioned above. It targets the cell [4][4] and, for every neighboring cell that has the same value as cell [$4$][$4$], it sets the color value to “3”.

//flood fill algorithm implemented in C++#include<iostream>using namespace std;// Dimentions of myScreen. You may change#define M 8#define N 8// A recursive function to replace// previous color 'currColor' at '(x, y)'// and all surrounding pixels of (x, y)// with new color 'newColor'void floodFill(int myScreen[][N], int x, int y, int currColor, int newColor){// Base casesif (x < 0 || x >= M || y < 0 || y >= N)return;if (myScreen[x][y] != currColor)return;if (myScreen[x][y] != currColor)return;// Replace the color at cell (x, y)myScreen[x][y] = newColor;// Recursively call for north, east, south and westfloodFill(myScreen, x+1, y, currColor, newColor);floodFill(myScreen, x-1, y, currColor, newColor);floodFill(myScreen, x, y+1, currColor, newColor);floodFill(myScreen, x, y-1, currColor, newColor);}// It mainly finds the previous color on (x, y) and// calls floodFill()void findColor(int myScreen[][N], int x, int y, int newColor){int currColor = myScreen[x][y];floodFill(myScreen, x, y, currColor, newColor);}// Driver program to test above functionint main(){int myScreen[M][N] ={{3, 2, 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},};//print initial screencout << "Initial myScreen : \n";for (int i=0; i<M; i++){for (int j=0; j<N; j++)cout << myScreen[i][j] << " ";cout << endl;}int x = 4, y = 4, newColor = 3;findColor(myScreen, x, y, newColor);cout<<endl;cout << "Updated myScreen : \n";//printing updated screenfor (int i=0; i<M; i++){for (int j=0; j<N; j++)cout << myScreen[i][j] << " ";cout << endl;}return 0;}

RELATED TAGS

flood

fill

java

algorithm

c++

Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Keep Exploring

Related Courses