Algoritmo de relleno de inundación – Part 1

Dada una pantalla 2D arr[][] donde cada arr[i][j] es un número entero que representa el color de ese píxel, también dada la ubicación de un píxel (X, Y) y un color C , la tarea es reemplazar el color del píxel dado y todos los píxeles adyacentes del mismo color con el color dado.
Ejemplo: 
 

Entrada: 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 
Salida: 
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 
Explicación: 
Los valores en la pantalla 2D dada indican los colores de los píxeles. X e Y son las coordenadas del pincel, C es el color que debe reemplazar el color anterior en la pantalla [X] [Y] y todos los píxeles circundantes con el mismo color. Por lo tanto, todos los 2 se reemplazan por 3. 
 

 

Enfoque BFS: la idea es usar el recorrido BFS para reemplazar el color con el nuevo color.
 

• Cree una cola vacía , digamos Q.
• Empuje la ubicación inicial del píxel como se indica en la entrada y aplíquele color de reemplazo.
• Iterar hasta que Q no esté vacío y abrir el Node frontal (posición de píxel).
• Verifique los píxeles adyacentes al píxel actual y colóquelos en la cola si es válido (no se coloreó con el color de reemplazo y tiene el mismo color que el color anterior).

A continuación se muestra la implementación del enfoque anterior:
 

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) {     vector<pair<int,int>> queue;       // Append the position of starting     // pixel of the component     pair<int,int> p(x,y);     queue.push_back(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[queue.size() - 1];         queue.pop_back();           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_back(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_back(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_back(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_back(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>

Producció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

 

Enfoque DFS: De manera similar, el enfoque DFS también se puede utilizar para implementar el algoritmo de relleno de inundación.