En MS-Paint, cuando llevamos el pincel a un píxel y hacemos clic, el color de la región de ese píxel se reemplaza con un nuevo color seleccionado. A continuación se presenta el enunciado del problema para realizar esta tarea.
Dada una pantalla 2D, la ubicación de un píxel en la pantalla y un color, reemplace el color del píxel dado y todos los píxeles adyacentes del mismo color con el color dado.
Ejemplo:
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},
};
Esta pregunta se puede resolver usando Recursión o BFS. Ambas soluciones se discuten a continuación.
Método 1 (usando recursividad): la idea es simple, primero reemplazamos el color del píxel actual, luego recurrimos a 4 puntos circundantes. El siguiente es un algoritmo detallado.
// A recursive function to replace
// previous color 'prevC' at '(x, y)'
// and all surrounding pixels of (x, y)
// with new color 'newC' and
floodFill(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);
La siguiente es la implementación del algoritmo anterior.
C++
// A C++ program to implement flood fill algorithm
#include<iostream>
using namespace std;
// Dimensions 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];
if(prevC==newC) return;
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;
}
}
//Updated by Arun Pandey
Java
// Java program to implement flood fill algorithm
class GFG
{
// Dimensions of paint screen
static int M = 8;
static int 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
static void floodFillUtil(int screen[][], 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;
// 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()
static void floodFill(int screen[][], int x, int y, int newC)
{
int prevC = screen[x][y];
if(prevC==newC) return;
floodFillUtil(screen, x, y, prevC, newC);
}
// Driver code
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},
};
int x = 4, y = 4, newC = 3;
floodFill(screen, x, y, newC);
System.out.println("Updated screen after call to floodFill: ");
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 has been contributed by 29AjayKumar
// Updated by Arun Pandey
Python3
# Python3 program to implement
# flood fill algorithm
# Dimensions of paint screen
M = 8
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
def floodFillUtil(screen, x, y, prevC, newC):
# Base cases
if (x < 0 or x >= M or y < 0 or
y >= N or screen[x][y] != prevC or
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()
def floodFill(screen, x, y, newC):
prevC = screen[x][y]
if(prevC==newC):
return
floodFillUtil(screen, x, y, prevC, newC)
# 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]]
x = 4
y = 4
newC = 3
floodFill(screen, x, y, newC)
print ("Updated screen after call to floodFill:")
for i in range(M):
for j in range(N):
print(screen[i][j], end = ' ')
print()
# This code is contributed by Ashutosh450
# Updated by Arun Pandey
C#
// C# program to implement
// flood fill algorithm
using System;
class GFG
{
// Dimensions of paint screen
static int M = 8;
static int 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
static void floodFillUtil(int [,]screen,
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;
// 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()
static void floodFill(int [,]screen, int x,
int y, int newC)
{
int prevC = screen[x, y];
if(prevC == newC)
return;
floodFillUtil(screen, x, y, prevC, newC);
}
// Driver code
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}};
int x = 4, y = 4, newC = 3;
floodFill(screen, x, y, newC);
Console.WriteLine("Updated screen after" +
"call to floodFill: ");
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 PrinciRaj1992
// Updated by Arun Pandey
Javascript
<script>
// JavaScript program to implement
// flood fill algorithm
// Dimensions of paint screen
var M = 8;
var 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
function floodFillUtil(screen, x, y, prevC, newC)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N) return;
if (screen[x][y] != prevC) 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()
function floodFill(screen, x, y, newC) {
var prevC = screen[x][y];
if (prevC == newC) return;
floodFillUtil(screen, x, y, prevC, newC);
}
// Driver code
var 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],
];
var x = 4,
y = 4,
newC = 3;
floodFill(screen, x, y, newC);
document.write("Updated screen after" + "call to floodFill: <br>");
for (var i = 0; i < M; i++) {
for (var j = 0; j < N; j++) document.write(screen[i][j] + " ");
document.write("<br>");
}
// This code is contributed by rdtank.
</script>
Producción
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
Complejidad temporal: O(M x N).
Espacio auxiliar: O (M x N), ya que se crea una pila implícita debido a la recursividad
Método 2 (usando el enfoque BFS):
Algoritmo para el enfoque basado en BFS:
- Crea una cola de parejas.
- Inserta un índice inicial dado en la cola.
- Marque el índice inicial como visitado en la array vis[][].
- Hasta que la cola no esté vacía, repita los pasos 4.1 a 4.6
- Tome el elemento frontal de la cola.
- Pop de la cola
- Almacene el valor/color actual en la coordenada extraída de la cola (precolor)
- Actualizar el valor/color del índice actual que se saca de la cola
- Verifique que las 4 direcciones, es decir, (x + 1, y), (x-1, y), (x, y + 1), (x, y-1) sean válidas o no y, si son válidas, verifique ese valor en ese la coordenada debe ser igual a precolor y el valor de esa coordenada en vis[][] es 0.
- Si todas las condiciones anteriores son verdaderas, presione la coordenada correspondiente en la cola y márquela como 1 en vis[][]
- Imprime la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ 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)
{
// Visiting array
int vis[101][101];
// Initializing 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;
// Until queue is empty
while (obj.empty() != 1)
{
// Extracting 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;
// Popping 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;
}
Java
// Java program for above approachimport java.io.*;
import java.util.*;
// Class to store the pairs
class Pair implements Comparable<Pair> {
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(Pair o) {
return second - o.second;
}
}
class GFG {
public static 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
public static void bfs(int n, int m, int data[][],int x, int y, int color)
{
// Visiting array
int vis[][]=new int[101][101];
// Initializing all as zero
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
vis[i][j]=0;
}
}
// Creating queue for bfs
Queue<Pair> obj = new LinkedList<>();
// Pushing pair of {x, y}
Pair pq=new Pair(x,y);
obj.add(pq);
// Marking {x, y} as visited
vis[x][y] = 1;
// Until queue is empty
while (!obj.isEmpty())
{
// Extracting front pair
Pair coord = obj.peek();
int x1 = coord.first;
int y1 = coord.second;
int preColor = data[x1][y1];
data[x1][y1] = color;
// Popping front pair of queue
obj.remove();
// For Upside Pixel or Cell
if ((validCoord(x1 + 1, y1, n, m)==1) && vis[x1 + 1][y1] == 0 && data[x1 + 1][y1] == preColor)
{
Pair p=new Pair(x1 +1, y1);
obj.add(p);
vis[x1 + 1][y1] = 1;
}
// For Downside Pixel or Cell
if ((validCoord(x1 - 1, y1, n, m)==1) && vis[x1 - 1][y1] == 0 && data[x1 - 1][y1] == preColor)
{
Pair p=new Pair(x1-1,y1);
obj.add(p);
vis[x1- 1][y1] = 1;
}
// For Right side Pixel or Cell
if ((validCoord(x1, y1 + 1, n, m)==1) && vis[x1][y1 + 1] == 0 && data[x1][y1 + 1] == preColor)
{
Pair p=new Pair(x1,y1 +1);
obj.add(p);
vis[x1][y1 + 1] = 1;
}
// For Left side Pixel or Cell
if ((validCoord(x1, y1 - 1, n, m)==1) && vis[x1][y1 - 1] == 0 && data[x1][y1 - 1] == preColor)
{
Pair p=new Pair(x1,y1 -1);
obj.add(p);
vis[x1][y1 - 1] = 1;
}
}
// Printing The Changed Matrix Of Pixels
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
System.out.print(data[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
public static void main (String[] args) {
int nn, mm, xx, yy, colorr;
nn = 8;
mm = 8;
int data[][] = {{ 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 },};
xx = 4; yy = 4; colorr = 3;
// Function Call
bfs(nn, mm, data, xx, yy, colorr);
}
}
// This code is contributed by Manu Pathria
Python3
# Python3 program for above approach
# Function to check valid coordinate
def validCoord(x, y, n, m):
if x < 0 or y < 0:
return 0
if x >= n or y >= m:
return 0
return 1
# Function to run bfs
def bfs(n, m, data, X, Y, color):
# Visiting array
vis = [[0 for i in range(101)] for j in range(101)]
# Creating queue for bfs
obj = []
# Pushing pair of {x, y}
obj.append([X, Y])
# Marking {x, y} as visited
vis[X][Y] = 1
# Until queue is empty
while len(obj) > 0:
# Extracting front pair
coord = obj[0]
x = coord[0]
y = coord[1]
preColor = data[x][y]
data[x][y] = color
# Popping front pair of queue
obj.pop(0)
# For Upside Pixel or Cell
if validCoord(x + 1, y, n, m) == 1 and vis[x + 1][y] == 0 and data[x + 1][y] == preColor:
obj.append([x + 1, y])
vis[x + 1][y] = 1
# For Downside Pixel or Cell
if validCoord(x - 1, y, n, m) == 1 and vis[x - 1][y] == 0 and data[x - 1][y] == preColor:
obj.append([x - 1, y])
vis[x - 1][y] = 1
# For Right side Pixel or Cell
if validCoord(x, y + 1, n, m) == 1 and vis[x][y + 1] == 0 and data[x][y + 1] == preColor:
obj.append([x, y + 1])
vis[x][y + 1] = 1
# For Left side Pixel or Cell
if validCoord(x, y - 1, n, m) == 1 and vis[x][y - 1] == 0 and data[x][y - 1] == preColor:
obj.append([x, y - 1])
vis[x][y - 1] = 1
# Printing The Changed Matrix Of Pixels
for i in range(n):
for j in range(m):
print(data[i][j], end = " ")
print()
print()
n = 8
m = 8
data = [
[ 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, y, color = 4, 4, 3
# Function Call
bfs(n, m, data, x, y, color)
# This code is contributed by decode2207.
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check valid coordinate
static 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
static void bfs(int n, int m, int[,] data, int X, int Y, int color)
{
// Visiting array
int[,] vis = new int[101,101];
// Creating queue for bfs
List<Tuple<int, int>> obj = new List<Tuple<int, int>>();
// Pushing pair of {x, y}
obj.Add(new Tuple<int,int>( X, Y ));
// Marking {x, y} as visited
vis[X,Y] = 1;
// Until queue is empty
while (obj.Count > 0)
{
// Extracting front pair
Tuple<int, int> coord = obj[0];
int x = coord.Item1;
int y = coord.Item2;
int preColor = data[x,y];
data[x,y] = color;
// Popping front pair of queue
obj.RemoveAt(0);
// For Upside Pixel or Cell
if (validCoord(x + 1, y, n, m) == 1
&& vis[x + 1,y] == 0
&& data[x + 1,y] == preColor)
{
obj.Add(new Tuple<int,int>(x + 1, y));
vis[x + 1,y] = 1;
}
// For Downside Pixel or Cell
if (validCoord(x - 1, y, n, m) == 1
&& vis[x - 1,y] == 0
&& data[x - 1,y] == preColor)
{
obj.Add(new Tuple<int,int>(x - 1, y));
vis[x - 1,y] = 1;
}
// For Right side Pixel or Cell
if (validCoord(x, y + 1, n, m) == 1
&& vis[x,y + 1] == 0
&& data[x,y + 1] == preColor)
{
obj.Add(new Tuple<int,int>(x, y + 1));
vis[x,y + 1] = 1;
}
// For Left side Pixel or Cell
if (validCoord(x, y - 1, n, m) == 1
&& vis[x,y - 1] == 0
&& data[x,y - 1] == preColor)
{
obj.Add(new Tuple<int,int>(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++)
{
Console.Write(data[i,j] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
static void Main() {
int n, m, x, y, color;
n = 8;
m = 8;
int[,] data = {
{ 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);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for above approach
// Function to check valid coordinate
function validCoord(x, y, n, m)
{
if (x < 0 || y < 0) {
return 0;
}
if (x >= n || y >= m) {
return 0;
}
return 1;
}
// Function to run bfs
function bfs(n, m, data, X, Y, color)
{
// Visiting array
let vis = new Array(101);
for(let i = 0; i < 101; i++)
{
vis[i] = new Array(101);
for(let j = 0; j < 101; j++)
{
vis[i][j] = 0;
}
}
// Creating queue for bfs
let obj = [];
// Pushing pair of {x, y}
obj.push([X, Y]);
// Marking {x, y} as visited
vis[X][Y] = 1;
// Until queue is empty
while (obj.length > 0)
{
// Extracting front pair
let coord = obj[0];
let x = coord[0];
let y = coord[1];
let preColor = data[x][y];
data[x][y] = color;
// Popping front pair of queue
obj.shift();
// For Upside Pixel or Cell
if (validCoord(x + 1, y, n, m) == 1
&& 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) == 1
&& 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) == 1
&& 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) == 1
&& 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 (let i = 0; i < n; i++)
{
for (let j = 0; j < m; j++)
{
document.write(data[i][j] + " ");
}
document.write("</br>");
}
document.write("</br>");
}
let n, m, x, y, color;
n = 8;
m = 8;
let data = [
[ 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);
// This code is contributed by mukesh07.
</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
Complejidad temporal: O(M x N).
Espacio Auxiliar: O(M x N),
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA