Dada una cuadrícula con diferentes colores en una celda diferente, cada color representado por un número diferente. La tarea es encontrar el componente conectado más grande en la red. La cuadrícula de componentes más grande se refiere a un conjunto máximo de celdas, de modo que puede moverse de cualquier celda a cualquier otra celda en este conjunto moviéndose solo entre las celdas adyacentes laterales del conjunto.
Ejemplos:
Aporte :
Rejilla de diferentes colores
Salida : 9
Mayor componente conectado de la red
Enfoque:
el enfoque es visualizar la cuadrícula dada como un gráfico en el que cada celda representa un Node separado del gráfico y cada Node está conectado a otros cuatro Nodes que se encuentran inmediatamente arriba, abajo, a la izquierda y a la derecha de esa cuadrícula. Ahora, haciendo una búsqueda BFS para cada Node del gráfico, encuentre todos los Nodes conectados al Node actual con el mismo valor de color que el Node actual .
Aquí está el gráfico para el ejemplo anterior:
Representación gráfica de la cuadrícula
.
En cada celda (i, j), se puede realizar un BFS. Los posibles movimientos desde una celda serán hacia la derecha, hacia la izquierda, hacia arriba o hacia abajo . Muévase solo a aquellas celdas que están dentro del rango y son del mismo color. Si los mismos Nodes han sido visitados anteriormente, entonces el valor del componente más grande de la cuadrícula se almacena en la array result[][] . Usando la memorización, reduzca la cantidad de BFS en cualquier celda. La array visited[][] se usa para marcar si la celda ha sido visitada anteriormente y el conteo almacena el conteo del componente conectado cuando se realiza un BFS para cada celda. Almacene el máximo del conteo e imprima la cuadrícula resultante usando la array result[][].
A continuación se muestra la ilustración del enfoque anterior:
C++
// CPP program to print the largest
// connected component in a grid
#include <bits/stdc++.h>
using namespace std;
const int n = 6;
const int m = 8;
// stores information about which cell
// are already visited in a particular BFS
int visited[n][m];
// result stores the final result grid
int result[n][m];
// stores the count of cells in the largest
// connected component
int COUNT;
// Function checks if a cell is valid i.e it
// is inside the grid and equal to the key
bool is_valid(int x, int y, int key, int input[n][m])
{
if (x < n && y < m && x >= 0 && y >= 0) {
if (visited[x][y] == false && input[x][y] == key)
return true;
else
return false;
}
else
return false;
}
// BFS to find all cells in
// connection with key = input[i][j]
void BFS(int x, int y, int i, int j, int input[n][m])
{
// terminating case for BFS
if (x != y)
return;
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int x_move[] = { 0, 0, 1, -1 };
int y_move[] = { 1, -1, 0, 0 };
// checks all four points connected with input[i][j]
for (int u = 0; u < 4; u++)
if (is_valid(i + y_move[u], j + x_move[u], x, input))
BFS(x, y, i + y_move[u], j + x_move[u], input);
}
// called every time before a BFS
// so that visited array is reset to zero
void reset_visited()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
visited[i][j] = 0;
}
// If a larger connected component
// is found this function is called
// to store information about that component.
void reset_result(int key, int input[n][m])
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] && input[i][j] == key)
result[i][j] = visited[i][j];
else
result[i][j] = 0;
}
}
}
// function to print the result
void print_result(int res)
{
cout << "The largest connected "
<< "component of the grid is :" << res << "\n";
// prints the largest component
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (result[i][j])
cout << result[i][j] << " ";
else
cout << ". ";
}
cout << "\n";
}
}
// function to calculate the largest connected
// component
void computeLargestConnectedGrid(int input[n][m])
{
int current_max = INT_MIN;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
BFS(input[i][j], input[i][j + 1], i, j, input);
// updating result
if (COUNT >= current_max) {
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
BFS(input[i][j], input[i + 1][j], i, j, input);
// updating result
if (COUNT >= current_max) {
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
// Drivers Code
int main()
{
int input[n][m] = { { 1, 4, 4, 4, 4, 3, 3, 1 },
{ 2, 1, 1, 4, 3, 3, 1, 1 },
{ 3, 2, 1, 1, 2, 3, 2, 1 },
{ 3, 3, 2, 1, 2, 2, 2, 2 },
{ 3, 1, 3, 1, 1, 4, 4, 4 },
{ 1, 1, 3, 1, 1, 4, 4, 4 } };
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
return 0;
}
Java
// Java program to print the largest
// connected component in a grid
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static final int n = 6;
static final int m = 8;
// stores information about which cell
// are already visited in a particular BFS
static final int visited[][] = new int [n][m];
// result stores the final result grid
static final int result[][] = new int [n][m];
// stores the count of
// cells in the largest
// connected component
static int COUNT;
// Function checks if a cell
// is valid i.e it is inside
// the grid and equal to the key
static boolean is_valid(int x, int y,
int key,
int input[][])
{
if (x < n && y < m &&
x >= 0 && y >= 0)
{
if (visited[x][y] == 0 &&
input[x][y] == key)
return true;
else
return false;
}
else
return false;
}
// BFS to find all cells in
// connection with key = input[i][j]
static void BFS(int x, int y, int i,
int j, int input[][])
{
// terminating case for BFS
if (x != y)
return;
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int x_move[] = { 0, 0, 1, -1 };
int y_move[] = { 1, -1, 0, 0 };
// checks all four points
// connected with input[i][j]
for (int u = 0; u < 4; u++)
if ((is_valid(i + y_move[u],
j + x_move[u], x, input)) == true)
BFS(x, y, i + y_move[u],
j + x_move[u], input);
}
// called every time before
// a BFS so that visited
// array is reset to zero
static void reset_visited()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
visited[i][j] = 0;
}
// If a larger connected component
// is found this function is
// called to store information
// about that component.
static void reset_result(int key,
int input[][])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] ==1 &&
input[i][j] == key)
result[i][j] = visited[i][j];
else
result[i][j] = 0;
}
}
}
// function to print the result
static void print_result(int res)
{
System.out.println ("The largest connected " +
"component of the grid is :" +
res );
// prints the largest component
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (result[i][j] != 0)
System.out.print(result[i][j] + " ");
else
System.out.print(". ");
}
System.out.println();
}
}
// function to calculate the
// largest connected component
static void computeLargestConnectedGrid(int input[][])
{
int current_max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
BFS(input[i][j], input[i][j + 1],
i, j, input);
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
BFS(input[i][j],
input[i + 1][j], i, j, input);
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
// Driver Code
public static void main(String args[])
{
int input[][] = {{1, 4, 4, 4, 4, 3, 3, 1},
{2, 1, 1, 4, 3, 3, 1, 1},
{3, 2, 1, 1, 2, 3, 2, 1},
{3, 3, 2, 1, 2, 2, 2, 2},
{3, 1, 3, 1, 1, 4, 4, 4},
{1, 1, 3, 1, 1, 4, 4, 4}};
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
}
}
// This code is contributed by Subhadeep
Python3
# Python3 program to print the largest
# connected component in a grid
n = 6;
m = 8;
# stores information about which cell
# are already visited in a particular BFS
visited = [[0 for j in range(m)]for i in range(n)]
# result stores the final result grid
result = [[0 for j in range(m)]for i in range(n)]
# stores the count of cells in the largest
# connected component
COUNT = 0
# Function checks if a cell is valid i.e it
# is inside the grid and equal to the key
def is_valid(x, y, key, input):
if (x < n and y < m and x >= 0 and y >= 0):
if (visited[x][y] == 0 and input[x][y] == key):
return True;
else:
return False;
else:
return False;
# BFS to find all cells in
# connection with key = input[i][j]
def BFS(x, y, i, j, input):
global COUNT
# terminating case for BFS
if (x != y):
return;
visited[i][j] = 1;
COUNT += 1
# x_move and y_move arrays
# are the possible movements
# in x or y direction
x_move = [ 0, 0, 1, -1 ]
y_move = [ 1, -1, 0, 0 ]
# checks all four points connected with input[i][j]
for u in range(4):
if (is_valid(i + y_move[u], j + x_move[u], x, input)):
BFS(x, y, i + y_move[u], j + x_move[u], input);
# called every time before a BFS
# so that visited array is reset to zero
def reset_visited():
for i in range(n):
for j in range(m):
visited[i][j] = 0
# If a larger connected component
# is found this function is called
# to store information about that component.
def reset_result(key, input):
for i in range(n):
for j in range(m):
if (visited[i][j] != 0 and input[i][j] == key):
result[i][j] = visited[i][j];
else:
result[i][j] = 0;
# function to print the result
def print_result(res):
print("The largest connected "+
"component of the grid is :" + str(res));
# prints the largest component
for i in range(n):
for j in range(m):
if (result[i][j] != 0):
print(result[i][j], end = ' ')
else:
print('. ',end = '')
print()
# function to calculate the largest connected
# component
def computeLargestConnectedGrid(input):
global COUNT
current_max = -10000000000
for i in range(n):
for j in range(m):
reset_visited();
COUNT = 0;
# checking cell to the right
if (j + 1 < m):
BFS(input[i][j], input[i][j + 1], i, j, input);
# updating result
if (COUNT >= current_max):
current_max = COUNT;
reset_result(input[i][j], input);
reset_visited();
COUNT = 0;
# checking cell downwards
if (i + 1 < n):
BFS(input[i][j], input[i + 1][j], i, j, input);
# updating result
if (COUNT >= current_max):
current_max = COUNT;
reset_result(input[i][j], input);
print_result(current_max);
# Drivers Code
if __name__=='__main__':
input = [ [ 1, 4, 4, 4, 4, 3, 3, 1 ],
[ 2, 1, 1, 4, 3, 3, 1, 1 ],
[ 3, 2, 1, 1, 2, 3, 2, 1 ],
[ 3, 3, 2, 1, 2, 2, 2, 2 ],
[ 3, 1, 3, 1, 1, 4, 4, 4 ],
[ 1, 1, 3, 1, 1, 4, 4, 4 ] ];
# function to compute the largest
# connected component in the grid
computeLargestConnectedGrid(input);
# This code is contributed by pratham76
C#
// C# program to print the largest
// connected component in a grid
using System;
class GFG
{
public const int n = 6;
public const int m = 8;
// stores information about which cell
// are already visited in a particular BFS
public static readonly int[][] visited =
RectangularArrays.ReturnRectangularIntArray(n, m);
// result stores the final result grid
public static readonly int[][] result =
RectangularArrays.ReturnRectangularIntArray(n, m);
// stores the count of cells in the
// largest connected component
public static int COUNT;
// Function checks if a cell is valid i.e
// it is inside the grid and equal to the key
internal static bool is_valid(int x, int y,
int key, int[][] input)
{
if (x < n && y < m &&
x >= 0 && y >= 0)
{
if (visited[x][y] == 0 &&
input[x][y] == key)
{
return true;
}
else
{
return false;
}
}
else
{
return false;
}
}
// BFS to find all cells in
// connection with key = input[i][j]
public static void BFS(int x, int y, int i,
int j, int[][] input)
{
// terminating case for BFS
if (x != y)
{
return;
}
visited[i][j] = 1;
COUNT++;
// x_move and y_move arrays
// are the possible movements
// in x or y direction
int[] x_move = new int[] {0, 0, 1, -1};
int[] y_move = new int[] {1, -1, 0, 0};
// checks all four points
// connected with input[i][j]
for (int u = 0; u < 4; u++)
{
if ((is_valid(i + y_move[u],
j + x_move[u], x, input)) == true)
{
BFS(x, y, i + y_move[u],
j + x_move[u], input);
}
}
}
// called every time before
// a BFS so that visited
// array is reset to zero
internal static void reset_visited()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
visited[i][j] = 0;
}
}
}
// If a larger connected component is
// found this function is called to
// store information about that component.
internal static void reset_result(int key,
int[][] input)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 1 &&
input[i][j] == key)
{
result[i][j] = visited[i][j];
}
else
{
result[i][j] = 0;
}
}
}
}
// function to print the result
internal static void print_result(int res)
{
Console.WriteLine("The largest connected " +
"component of the grid is :" + res);
// prints the largest component
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (result[i][j] != 0)
{
Console.Write(result[i][j] + " ");
}
else
{
Console.Write(". ");
}
}
Console.WriteLine();
}
}
// function to calculate the
// largest connected component
public static void computeLargestConnectedGrid(int[][] input)
{
int current_max = int.MinValue;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
reset_visited();
COUNT = 0;
// checking cell to the right
if (j + 1 < m)
{
BFS(input[i][j], input[i][j + 1],
i, j, input);
}
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
reset_visited();
COUNT = 0;
// checking cell downwards
if (i + 1 < n)
{
BFS(input[i][j], input[i + 1][j],
i, j, input);
}
// updating result
if (COUNT >= current_max)
{
current_max = COUNT;
reset_result(input[i][j], input);
}
}
}
print_result(current_max);
}
public static class RectangularArrays
{
public static int[][] ReturnRectangularIntArray(int size1,
int size2)
{
int[][] newArray = new int[size1][];
for (int array1 = 0; array1 < size1; array1++)
{
newArray[array1] = new int[size2];
}
return newArray;
}
}
// Driver Code
public static void Main(string[] args)
{
int[][] input = new int[][]
{
new int[] {1, 4, 4, 4, 4, 3, 3, 1},
new int[] {2, 1, 1, 4, 3, 3, 1, 1},
new int[] {3, 2, 1, 1, 2, 3, 2, 1},
new int[] {3, 3, 2, 1, 2, 2, 2, 2},
new int[] {3, 1, 3, 1, 1, 4, 4, 4},
new int[] {1, 1, 3, 1, 1, 4, 4, 4}
};
// function to compute the largest
// connected component in the grid
computeLargestConnectedGrid(input);
}
}
// This code is contributed by Shrikant13
Producción:
The largest connected component of the grid is :9 . . . . . . . . . 1 1 . . . . . . . 1 1 . . . . . . . 1 . . . . . . . 1 1 . . . . . . 1 1 . . .