If you haven't played Kami-2, I would urge you to check it out on the Play store or App store. It's a beautifully designed puzzle in which the main goal is to convert all the tiles on the board to a single color in as few moves as possible.
A short gif on the same :
The basic working can be boiled down to 2 main functions.
1> Look around the adjacent neighbor cells.
2> If they're the same color as current cell, change their color and repeat.
This is a question asked at all the "FAANG" interviews
For the sake of better understanding consider this image grid :
And we want to convert all red's to blue.
Step 1 : Choose one red cell and look around the adjacent neighboring cells.
We basically see all 4 directions, North, South, East, West.
Converting that to code :
let dirs = [[-1,0],[0,1],[0,1],[-1,0]];
let arr = []; // for storing the cells
let dx = 2;
let dy = 2;
for(int dir:dirs){
let x = dir[0]+dx;
let y = dir[1]+dy;
if(cell[x][y] == 'red'){
arr.push([x,y]);
}
}
Step 2: Convert all the red cells to blue cells and repeat step 1 on the converted cells.
cell[x][y] = 'blue'
Here, we have two options to go with, Depth First Traversal and Breadth-First Traversal. Time Complexity for both will be O(mn) on average.
Let's implement both.
Depth First Traversal:
var dfs = function(image,sr,sc,newColor,oldColor){
if(sr<0 || sc<0 || sr>=image.length || sc>=image[0].length || image[sr][sc] != oldColor)
return;
image[sr][sc] = newColor;
dfs(image,sr-1,sc,newColor,oldColor);
dfs(image,sr,sc+1,newColor,oldColor);
dfs(image,sr+1,sc,newColor,oldColor);
dfs(image,sr,sc-1,newColor,oldColor);
}
var floodFill = function(image, sr, sc, newColor) {
let oldColor = image[sr][sc];
if(oldColor == newColor) return image;
dfs(image,sr,sc,newColor,oldColor);
return image;
};
Breadth-First Traversal:
var floodFill = function(image, sr, sc, newColor) {
let oldColor = image[sr][sc];
if(oldColor == newColor) return image;
let queue = [];
queue.push([sr,sc]);
let dirs = [[-1,0],[0,1],[1,0],[0,-1]];
while(queue.length>0){
let size = queue.length;
for(let i=0;i<size;i++){
let node = queue.shift();
let dx = node[0];
let dy = node[1];
image[dx][dy] = newColor;
for(let dir of dirs){
let x = dx+dir[0];
let y = dy+dir[1];
if(x<0 || y<0 || x>=image.length || y>=image[0].length || image[x][y] != oldColor) continue;
queue.push([x,y]);
}
}
}
return image;
};
I hope you understood the flood fill algorithm and liked my explanation.
Happy coding! :)
github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Algorithm/FloodFill.js
Top comments (0)