Flood Fill Algorithm

Last Updated : 09 Aug, 2023

Given a 2D screen arr[][] where each arr[i][j] is an integer representing the color of that pixel, also given the location of a pixel (X, Y) and a color C, the task is to replace the color of the given pixel and all the adjacent same-colored pixels with the given color.

Example:

Input: arr[][] = {
{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, C = 3
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
Explanation:
The values in the given 2D screen indicate colors of the pixels. X and Y are coordinates of the brush, C is the color that should replace the previous color on screen[X][Y] and all surrounding pixels with the same color. Hence all the 2 are replaced with 3.

BFS Approach: The idea is to use BFS traversal to replace the color with the new color.

Create an empty queue let’s say Q.
Push the starting location of the pixel as given in the input and apply the replacement color to it.
Iterate until Q is not empty and pop the front node (pixel position).
Check the pixels adjacent to the current pixel and push them into the queue if valid (had not been colored with replacement color and have the same color as the old color).

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if
// the given pixel is valid
bool isValid(int screen[][8], int m, int n, int x, int y,
             int prevC, int newC)
{
    if (x < 0 || x >= m || y < 0 || y >= n
        || screen[x][y] != prevC || screen[x][y] == newC)
        return false;
    return true;
}
 
// FloodFill function
void floodFill(int screen[][8], int m, int n, int x, int y,
               int prevC, int newC)
{
    queue<pair<int, int> > queue;
 
    // Append the position of starting
    // pixel of the component
    pair<int, int> p(x, y);
    queue.push(p);
 
    // Color the pixel with the new color
    screen[x][y] = newC;
 
    // While the queue is not empty i.e. the
    // whole component having prevC color
    // is not colored with newC color
    while (queue.size() > 0) {
        // Dequeue the front node
        pair<int, int> currPixel = queue.front();
        queue.pop();
 
        int posX = currPixel.first;
        int posY = currPixel.second;
 
        // Check if the adjacent
        // pixels are valid
        if (isValid(screen, m, n, posX + 1, posY, prevC,
                    newC)) {
            // Color with newC
            // if valid and enqueue
            screen[posX + 1][posY] = newC;
            p.first = posX + 1;
            p.second = posY;
            queue.push(p);
        }
 
        if (isValid(screen, m, n, posX - 1, posY, prevC,
                    newC)) {
            screen[posX - 1][posY] = newC;
            p.first = posX - 1;
            p.second = posY;
            queue.push(p);
        }
 
        if (isValid(screen, m, n, posX, posY + 1, prevC,
                    newC)) {
            screen[posX][posY + 1] = newC;
            p.first = posX;
            p.second = posY + 1;
            queue.push(p);
        }
 
        if (isValid(screen, m, n, posX, posY - 1, prevC,
                    newC)) {
            screen[posX][posY - 1] = newC;
            p.first = posX;
            p.second = posY - 1;
            queue.push(p);
        }
    }
}
 
int main()
{
    int screen[][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 } };
 
    // Row of the display
    int m = 8;
 
    // Column of the display
    int n = 8;
 
    // Co-ordinate provided by the user
    int x = 4;
    int y = 4;
 
    // Current color at that co-ordinate
    int prevC = screen[x][y];
 
    // New color that has to be filled
    int newC = 3;
    floodFill(screen, m, n, x, y, prevC, newC);
 
    // Printing the updated screen
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << screen[i][j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}
 
// This code is contributed by suresh07.

Java

// Java implementation of the approach
import java.util.*;
import java.awt.Point;
public class Main
{
    // Function that returns true if
    // the given pixel is valid
    static boolean isValid(int[][] screen, int m, int n, int x, int y, int prevC, int newC)
    {
        if(x < 0 || x >= m || y < 0 || y >= n || screen[x][y] != prevC
           || screen[x][y]== newC)
            return false;
        return true;
    }
   
   
    // FloodFill function
    static void floodFill(int[][] screen, int m, int n, int x, int y, int prevC, int newC)
    {
        Vector<Point> queue = new Vector<Point>();
   
        // Append the position of starting
        // pixel of the component
        queue.add(new Point(x, y));
   
        // Color the pixel with the new color
        screen[x][y] = newC;
   
        // While the queue is not empty i.e. the
        // whole component having prevC color
        // is not colored with newC color
        while(queue.size() > 0)
        {
            // Dequeue the front node
            Point currPixel = queue.get(queue.size() - 1);
            queue.remove(queue.size() - 1);
   
            int posX = currPixel.x;
            int posY = currPixel.y;
   
            // Check if the adjacent
            // pixels are valid
            if(isValid(screen, m, n, posX + 1, posY, prevC, newC))
            {
                // Color with newC
                // if valid and enqueue
                screen[posX + 1][posY] = newC;
                queue.add(new Point(posX + 1, posY));
            }
   
            if(isValid(screen, m, n, posX-1, posY, prevC, newC))
            {
                screen[posX-1][posY]= newC;
                queue.add(new Point(posX-1, posY));
            }
   
            if(isValid(screen, m, n, posX, posY + 1, prevC, newC))
            {
                screen[posX][posY + 1]= newC;
                queue.add(new Point(posX, posY + 1));
            }
   
            if(isValid(screen, m, n, posX, posY-1, prevC, newC))
            {
                screen[posX][posY-1]= newC;
                queue.add(new Point(posX, posY-1));
            }
        }
    }
     
    public static void main(String[] args) {
        int[][] screen ={
        {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}};
       
        // Row of the display
        int m = screen.length;
       
        // Column of the display
        int n = screen.length;
       
        // Co-ordinate provided by the user
        int x = 4;
        int y = 4;
       
        // Current color at that co-ordinate
        int prevC = screen[x][y];
       
        // New color that has to be filled
        int newC = 3;
        floodFill(screen, m, n, x, y, prevC, newC);
       
        // Printing the updated screen
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                System.out.print(screen[i][j] + " ");
            }
            System.out.println();
        }
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 implementation of the approach
 
# Function that returns true if 
# the given pixel is valid
def isValid(screen, m, n, x, y, prevC, newC):
    if x<0 or x>= m\
       or y<0 or y>= n or\
       screen[x][y]!= prevC\
       or screen[x][y]== newC:
        return False
    return True
 
 
# FloodFill function
def floodFill(screen,  
            m, n, x,  
            y, prevC, newC):
    queue = []
     
    # Append the position of starting 
    # pixel of the component
    queue.append([x, y])
 
    # Color the pixel with the new color
    screen[x][y] = newC
 
    # While the queue is not empty i.e. the 
    # whole component having prevC color 
    # is not colored with newC color
    while queue:
         
        # Dequeue the front node
        currPixel = queue.pop()
         
        posX = currPixel[0]
        posY = currPixel[1]
         
        # Check if the adjacent
        # pixels are valid
        if isValid(screen, m, n,  
                posX + 1, posY,  
                        prevC, newC):
             
            # Color with newC
            # if valid and enqueue
            screen[posX + 1][posY] = newC
            queue.append([posX + 1, posY])
         
        if isValid(screen, m, n,  
                    posX-1, posY,  
                        prevC, newC):
            screen[posX-1][posY]= newC
            queue.append([posX-1, posY])
         
        if isValid(screen, m, n,  
                posX, posY + 1,  
                        prevC, newC):
            screen[posX][posY + 1]= newC
            queue.append([posX, posY + 1])
         
        if isValid(screen, m, n,  
                    posX, posY-1,  
                        prevC, newC):
            screen[posX][posY-1]= newC
            queue.append([posX, posY-1])
 
 
 
# Driver code
screen =[
[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], 
    ]
     
# Row of the display
m = len(screen)
 
# Column of the display
n = len(screen[0])
 
# Co-ordinate provided by the user
x = 4
y = 4
 
# Current color at that co-ordinate
prevC = screen[x][y]
 
# New color that has to be filled
newC = 3
 
floodFill(screen, m, n, x, y, prevC, newC)
 
 
# Printing the updated screen
for i in range(m):
    for j in range(n):
        print(screen[i][j], end =' ')
    print()

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function that returns true if
    // the given pixel is valid
    static bool isValid(int[,] screen, int m, int n, int x, int y, int prevC, int newC)
    {
        if(x < 0 || x >= m || y < 0 || y >= n || screen[x, y] != prevC
           || screen[x,y]== newC)
            return false;
        return true;
    }
  
  
    // FloodFill function
    static void floodFill(int[,] screen, int m, int n, int x, int y, int prevC, int newC)
    {
        List<Tuple<int,int>> queue = new List<Tuple<int,int>>();
  
        // Append the position of starting
        // pixel of the component
        queue.Add(new Tuple<int,int>(x, y));
  
        // Color the pixel with the new color
        screen[x,y] = newC;
  
        // While the queue is not empty i.e. the
        // whole component having prevC color
        // is not colored with newC color
        while(queue.Count > 0)
        {
            // Dequeue the front node
            Tuple<int,int> currPixel = queue[queue.Count - 1];
            queue.RemoveAt(queue.Count - 1);
  
            int posX = currPixel.Item1;
            int posY = currPixel.Item2;
  
            // Check if the adjacent
            // pixels are valid
            if(isValid(screen, m, n, posX + 1, posY, prevC, newC))
            {
                // Color with newC
                // if valid and enqueue
                screen[posX + 1,posY] = newC;
                queue.Add(new Tuple<int,int>(posX + 1, posY));
            }
  
            if(isValid(screen, m, n, posX-1, posY, prevC, newC))
            {
                screen[posX-1,posY]= newC;
                queue.Add(new Tuple<int,int>(posX-1, posY));
            }
  
            if(isValid(screen, m, n, posX, posY + 1, prevC, newC))
            {
                screen[posX,posY + 1]= newC;
                queue.Add(new Tuple<int,int>(posX, posY + 1));
            }
  
            if(isValid(screen, m, n, posX, posY-1, prevC, newC))
            {
                screen[posX,posY-1]= newC;
                queue.Add(new Tuple<int,int>(posX, posY-1));
            }
        }
    }
     
  static void Main() {
    int[,] screen ={
    {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}};
  
    // Row of the display
    int m = screen.GetLength(0);
  
    // Column of the display
    int n = screen.GetLength(1);
  
    // Co-ordinate provided by the user
    int x = 4;
    int y = 4;
  
    // Current color at that co-ordinate
    int prevC = screen[x,y];
  
    // New color that has to be filled
    int newC = 3; 
    floodFill(screen, m, n, x, y, prevC, newC);
  
    // Printing the updated screen
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            Console.Write(screen[i,j] + " ");
        }
        Console.WriteLine();
    }
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
    // Javascript implementation of the approach
     
    // Function that returns true if
    // the given pixel is valid
    function isValid(screen, m, n, x, y, prevC, newC)
    {
        if(x<0 || x>= m || y<0 || y>= n || screen[x][y]!= prevC
           || screen[x][y]== newC)
            return false;
        return true;
    }
 
 
    // FloodFill function
    function floodFill(screen, m, n, x, y, prevC, newC)
    {
        let queue = [];
 
        // Append the position of starting
        // pixel of the component
        queue.push([x, y]);
 
        // Color the pixel with the new color
        screen[x][y] = newC;
 
        // While the queue is not empty i.e. the
        // whole component having prevC color
        // is not colored with newC color
        while(queue.length > 0)
        {
            // Dequeue the front node
            currPixel = queue[queue.length - 1];
            queue.pop();
 
            let posX = currPixel[0];
            let posY = currPixel[1];
 
            // Check if the adjacent
            // pixels are valid
            if(isValid(screen, m, n, posX + 1, posY, prevC, newC))
            {
                // Color with newC
                // if valid and enqueue
                screen[posX + 1][posY] = newC;
                queue.push([posX + 1, posY]);
            }
 
            if(isValid(screen, m, n, posX-1, posY, prevC, newC))
            {
                screen[posX-1][posY]= newC;
                queue.push([posX-1, posY]);
            }
 
            if(isValid(screen, m, n, posX, posY + 1, prevC, newC))
            {
                screen[posX][posY + 1]= newC;
                queue.push([posX, posY + 1]);
            }
 
            if(isValid(screen, m, n, posX, posY-1, prevC, newC))
            {
                screen[posX][posY-1]= newC;
                queue.push([posX, posY-1]);
            }
        }
    }
     
    let screen =[
    [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]];
 
    // Row of the display
    let m = screen.length;
 
    // Column of the display
    let n = screen[0].length;
 
    // Co-ordinate provided by the user
    let x = 4;
    let y = 4;
 
    // Current color at that co-ordinate
    let prevC = screen[x][y];
 
    // New color that has to be filled
    let newC = 3;
 
    floodFill(screen, m, n, x, y, prevC, newC);
 
 
    // Printing the updated screen
    for(let i = 0; i < m; i++)
    {
        for(let j = 0; j < n; j++)
        {
            document.write(screen[i][j] + " ");
        }
        document.write("</br>");
    }
     
    // This code is contributed by divyesh072019.
</script>

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

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)

An Approach using DFS:

Change the color of the source row and source column with the given color
Do DFS in four direction

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// DFS Approach 
void dfs(int row,int col,vector<vector<int>> &image,vector<vector<int>>& ans,int newColor,int iniColor,int n,int m,int delrow[],int delcol[]){
     
    // Marking it as the newColor
    ans[row][col] = newColor;
    for(int i=0;i<4;i++){
        int nrow = row + delrow[i];
        int ncol = col + delcol[i];
          // Checking Out Of Bound Condition
        if(nrow>=0 && ncol>=0 && nrow<n && ncol<m && image[nrow][ncol]==iniColor && ans[nrow][ncol]!=newColor){
            dfs(nrow,ncol,image,ans,newColor,iniColor,n,m,delrow,delcol);
        }
    }
     
}
// FloodFill Function
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        // Code here 
        vector<vector<int>> ans = image;
        int n = image.size();
        int m = image[0].size();
          // Initial Color 
        int iniColor = image[sr][sc];
          // vectors for changing of rows and column direction
          // UP LEFT DOWN RIGHT
        int delrow[] = {-1,0,+1,0};
        int delcol[] = {0,+1,0,-1};
          // Calling dfs function
        dfs(sr,sc,image,ans,newColor,iniColor,n,m,delrow,delcol);
        return ans;
    }
 
// Driver code
int main()
{
    vector<vector<int> > screen
        = { {1, 1, 1},
            {1, 1, 0},
            {1, 0, 1} };
 
    int n = screen.size();
      int m = screen[0].size();
    // Co-ordinate provided by the user
    int x = 1;
    int y = 1;
 
    // New color that has to be filled
    int newC = 3;
    vector<vector<int>> ans = floodFill(screen, x, y, newC);
     
 
    // Printing the updated screen
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}
 
// This code is contributed by Tanishq Raj.

Java

import java.util.ArrayList;
 
public class FloodFill {
    // Floodfill function
    public static void floodFill(int[][] screen, int sr,
                                 int sc, int row, int col,
                                 int source, int color)
    {
        // Condition for checking out of bounds
        if (sr < 0 || sr >= row || sc < 0 || sc >= col)
            return;
 
        if (screen[sr][sc] != source)
            return;
 
        screen[sr][sc] = color;
        floodFill(screen, sr - 1, sc, row, col, source,
                  color); // left
        floodFill(screen, sr + 1, sc, row, col, source,
                  color); // right
        floodFill(screen, sr, sc + 1, row, col, source,
                  color); // top
        floodFill(screen, sr, sc - 1, row, col, source,
                  color); // bottom
    }
 
    public static void main(String[] args)
    {
        int[][] screen = { { 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 } };
 
        // Row of the display
        int m = 8;
 
        // Column of the display
        int n = 8;
 
        // Co-ordinate provided by the user
        int x = 4;
        int y = 4;
 
        // Current color at that co-ordinate
        int prevC = screen[x][y];
 
        // New color that has to be filled
        int newC = 3;
 
        floodFill(screen, x, y, m, n, prevC, newC);
 
        // Printing the updated screen
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(screen[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Python3

from typing import List, Tuple
 
 
def flood_fill(screen: List[List[int]], sr: int, sc: int, row: int, col: int, source: int, color: int) -> None:
    # Condition for checking out of bounds
    if sr < 0 or sr >= row or sc < 0 or sc >= col:
        return
 
    if screen[sr][sc] != source:
        return
 
    screen[sr][sc] = color
    flood_fill(screen, sr - 1, sc, row, col, source, color)  # left
    flood_fill(screen, sr + 1, sc, row, col, source, color)  # right
    flood_fill(screen, sr, sc + 1, row, col, source, color)  # top
    flood_fill(screen, sr, sc - 1, row, col, source, color)  # bottom
 
 
if __name__ == "__main__":
    screen = [
        [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]
    ]
 
    # Row of the display
    m = 8
 
    # Column of the display
    n = 8
 
    # Coordinate provided by the user
    x = 4
    y = 4
 
    # Current color at that coordinate
    prevC = screen[x][y]
 
    # New color that has to be filled
    newC = 3
 
    flood_fill(screen, x, y, m, n, prevC, newC)
 
    # Printing the updated screen
    for i in range(m):
        for j in range(n):
            print(screen[i][j], end=" ")
        print()

C#

using System;
 
namespace FloodFill {
class Program {
    static void Main(string[] args)
    {
        int[, ] screen = { { 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 } };
 
        // Dimensions of the screen
        int m = 8;
        int n = 8;
 
        // Coordinates provided by the user
        int x = 4;
        int y = 4;
 
        // Current color at the given coordinate
        int prevC = screen[x, y];
 
        // New color to fill
        int newC = 3;
 
        FloodFill(screen, x, y, m, n, prevC, newC);
 
        // Printing the updated screen
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Console.Write(screen[i, j] + " ");
            }
            Console.WriteLine();
        }
 
        Console.ReadKey();
    }
 
    // Flood fill function
    static void FloodFill(int[, ] screen, int sr, int sc,
                          int row, int col, int source,
                          int color)
    {
        // Check for out of bounds
        if (sr < 0 || sr >= row || sc < 0 || sc >= col)
            return;
 
        // Check if the current pixel is not equal to the
        // source color
        if (screen[sr, sc] != source)
            return;
 
        screen[sr, sc] = color;
 
        // Recursively fill the surrounding pixels
        FloodFill(screen, sr - 1, sc, row, col, source,
                  color); // left
        FloodFill(screen, sr + 1, sc, row, col, source,
                  color); // right
        FloodFill(screen, sr, sc + 1, row, col, source,
                  color); // top
        FloodFill(screen, sr, sc - 1, row, col, source,
                  color); // bottom
    }
}
}

Javascript

// JavaScript implementation of the approach
 
 
// Floodfill function
function floodFill(screen, sr, sc, row, col, source, color)
{
    // Condition for checking out of bounds
    if (sr < 0 || sr >= row || sc < 0 || sc >= col) return;
 
    if (screen[sr][sc] != source) return;
 
    screen[sr][sc] = color;
    floodFill(screen, sr - 1, sc, row, col, source, color); // left
    floodFill(screen, sr + 1, sc, row, col, source, color); // right
    floodFill(screen, sr, sc + 1, row, col, source, color); // top
    floodFill(screen, sr, sc - 1, row, col, source, color); // bottom
}
 
// Driver code
let screen = [  [ 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 ] ];
 
 
// Row of the display
let m = 8;
 
// Column of the display
let n = 8;
 
// Co-ordinate provided by the user
let x = 4;
let y = 4;
 
// Current color at that co-ordinate
let prevC = screen[x][y];
 
// New color that has to be filled
let newC = 3;
 
floodFill(screen, x, y, m, n, prevC, newC);
 
// Printing the updated screen
for (let i = 0; i < m; i++) {
    let temp = "";
    for (let j = 0; j < n; j++) {
           document.write(screen[i][j] + " ");
    }
    document.write("</br>");
}
 
 
// This code is contributed by Gautam goel

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

Time Complexity: O(m*n)
Auxiliary Space: O(m + n), due to the recursive call stack.

A

Archana choudhary

Improve

Previous Article

Sliding Window Maximum (Maximum of all subarrays of size K)

Minimum time required to rotten all oranges

Similar Reads

Difference Between Flood-fill and Boundary-fill Algorithm

Flood-fill Algorithm: Flood fill algorithm is also known as a seed fill algorithm. It determines the area which is connected to a given node in a multi-dimensional array. This algorithm works by filling or recolouring a selected area containing different colours at the inside portion and therefore the boundary of the image. It is often illustrated

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. Examp

Java Applet | Implementing Flood Fill algorithm

Flood Fill Algorithm is to replace a certain closed or a similarly colored field with a specified color. The use of the FloodFill algorithm can be seen in paints and other games such as minesweeper.In this article, FloodFill is used for a connected area by a specified color, in Java Applet by using the FloodFill algorithm.There are two approaches t

Boundary Fill Algorithm

Prerequisite : Flood fill algorithm, Scan-line polygon fillingIntroduction : Boundary Fill Algorithm starts at a pixel inside the polygon to be filled and paints the interior proceeding outwards towards the boundary. This algorithm works only if the color with which the region has to be filled and the color of the boundary of the region are differe

Fill 8 numbers in grid with given conditions

Place the numbers 1, 2, 3, 4, 5, 6, 7, 8 into the eight circles in the figure given below, in such a way that no number is adjacent to a number that is next to it in the sequence. For example, 1 should not be adjacent to 2 but can be adjacent to 3, 4, 5, 6, 7, 8. Similarly for others. Naive Algorithm The Naive Algorithm is to generate all possible

Count the number of ways to fill K boxes with N distinct items

Given two values N and K. Find the number of ways to arrange the N distinct items in the boxes such that exactly K (K<N) boxes are used from the N distinct boxes. The answer can be very large so return the answer modulo 109 + 7.Note: 1 <= N <= K <= 105. Prerequisites: Factorial of a number, Compute nCr % p Examples: Input: N = 5, k = 5

Minimum number of integers required to fill the NxM grid

Given a grid of size (NxM) is to be filled with integers. Filling of cells in the grid should be done in the following manner: let A, B and C are three cell and, B and C shared a side with A.Value of cell B and C must be distinct.Let L be the number of distinct integers in a grid.Each cell should contain value from 1 to L. The task is to find the m

Minimum number of square tiles required to fill the rectangular floor

Given a rectangular floor of (M X N) meters is to be paved with square tiles of (s X s). The task is to find the minimum number of tiles required to pave the rectangular floor. Constraints: It's allowed to cover the surface larger than the floor, but the floor has to be covered.It's not allowed to break the tiles.The sides of tiles should be parall

Minimum time required to fill a cistern using N pipes

Given the time required by a total of N+1 pipes where N pipes are used to fill the Cistern and a single pipe is used to empty the Cistern. The task is to Calculate the amount of time in which the Cistern will get filled if all the N+1 pipes are opened together. Examples: Input: n = 2, pipe1 = 12 hours, pipe2 = 14 hours, emptypipe = 30 hours Output:

Minimum number of bottles required to fill K glasses

Given N glasses having water, and a list A of each of their capacity. The task is to find the minimum number of bottles required to fill out exactly K glasses. The capacity of each bottle is 100 units. Examples: Input: N = 4, K = 3, arr[] = {200, 150, 140, 300} Output: 5 We have to fill out exactly 3 glasses. So we fill out 140, 150, 200 whose sum

Article Tags :

Practice Tags :