Dada una array mat[][] que contiene solo 0 s y 1 s, y una array queries[] , la tarea es para cada consulta, digamos k , es encontrar el número de componentes de cuadrícula conectados ( celdas que consisten en 1 s ) de tamaño k .
Nota: dos celdas están conectadas si comparten un borde en la dirección hacia arriba, abajo, izquierda y derecha, no en diagonal.
Ejemplo:
Entrada: mat[][] = [[1 1 1 1 1 1],
[1 1 0 0 0 0],
[0 0 0 1 1 1],
[0 0 0 1 1 1],
[0 0 1 0 0 0],
[1 0 0 0 0 0]]
consultas[] =[6, 1, 8, 2] Salida: [1, 2, 1, 0] Explicación: Hay 4 componentes conectados de tamaños 8, 6, 1, 1 respectivamente, por lo tanto, la salida de la array de consultas es [1, 2, 1, 0]. Podemos ver que en la imagen está marcado el número de componentes conectados de diferentes tamaños:Entrada: array[][] = [[1 1 0 0 0],
[1 0 0 1 0],
[0 0 1 1 0],
[1 1 0 0 0]]
consultas[]= [3, 1, 2, 4]
Salida: [2, 0, 1, 0]
Explicación: el número de componentes conectados de tamaños 3, 2 son 2, 1 todos los demás tamaños son cero, por lo tanto, la array de salida es [2, 0, 1, 0]
Enfoque: la idea es contar y almacenar la frecuencia de la cantidad de componentes conectados de todos los tamaños en un mapa desordenado usando BFS / DFS en la cuadrícula, luego podemos iterar sobre la array de consultas y asignar el conteo de componentes conectados para cada uno. tamaño dado en la array.
Los siguientes son los pasos para resolver el problema:
- Iterar a través de la array y realizar BFS desde la celda no visitada que contiene «1»
- Compruebe si las celdas adyacentes válidas no visitadas contienen 1 y coloque estas celdas en la cola.
- Repita los dos pasos anteriores para todas las celdas no visitadas que tengan 1.
- Imprime la array que tiene el número de componentes conectados para cada tamaño dado en las consultas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
const int n = 6;
const int m = 6;
const int dx[] = { 0, 1, -1, 0 };
const int dy[] = { 1, 0, 0, -1 };
// stores information about which cell
// are already visited in a particular BFS
int visited[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 1
bool is_valid(int x, int y, int matrix[n][m])
{
if (x < n && y < m && x >= 0 && y >= 0) {
if (visited[x][y] == false
&& matrix[x][y] == 1)
return true;
else
return false;
}
else
return false;
}
// Map to count the frequency of
// each connected component
map<int, int> mp;
// function to calculate the
// largest connected component
void findComponentSize(int matrix[n][m])
{
// Iterate over every cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && matrix[i][j] == 1) {
COUNT = 0;
// Stores the indices of the matrix cells
queue<pair<int, int> > q;
// Mark the starting cell as visited
// and push it into the queue
q.push({ i, j });
visited[i][j] = true;
// Iterate while the queue
// is not empty
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first, y = p.second;
COUNT++;
// Go to the adjacent cells
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (is_valid(newX, newY, matrix)) {
q.push({ newX, newY });
visited[newX][newY] = true;
}
}
}
mp[COUNT]++;
}
}
}
}
// Drivers Code
int main()
{
// Given input array of 1s and 0s
int matrix[n][m]
= { { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };
// queries array
int queries[] = { 6, 1, 8, 2 };
// sizeof queries array
int N = sizeof(queries) / sizeof(queries[0]);
// Initialize all cells unvisited
memset(visited, false, sizeof visited);
// Count the frequency of each connected component
findComponentSize(matrix);
// Iterate over the given queries array and
// And answer the queries
for (int i = 0; i < N; i++)
cout << mp[queries[i]] << " ";
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int n = 6;
static int m = 6;
static int dx[] = { 0, 1, -1, 0 };
static int dy[] = { 1, 0, 0, -1 };
// stores information about which cell
// are already visited in a particular BFS
static int [][]visited = new int[n][m];
// Stores the final result grid
static 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 1
static boolean is_valid(int x, int y, int matrix[][])
{
if (x < n && y < m && x >= 0 && y >= 0) {
if (visited[x][y] == 0
&& matrix[x][y] == 1)
return true;
else
return false;
}
else
return false;
}
// Map to count the frequency of
// each connected component
static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
// function to calculate the
// largest connected component
static void findComponentSize(int matrix[][])
{
// Iterate over every cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j]==0 && matrix[i][j] == 1) {
COUNT = 0;
// Stores the indices of the matrix cells
Queue<pair > q = new LinkedList<>();
// Mark the starting cell as visited
// and push it into the queue
q.add(new pair( i, j ));
visited[i][j] = 1;
// Iterate while the queue
// is not empty
while (!q.isEmpty()) {
pair p = q.peek();
q.remove();
int x = p.first, y = p.second;
COUNT++;
// Go to the adjacent cells
for (int k = 0; k < 4; k++) {
int newX = x + dx[k];
int newY = y + dy[k];
if (is_valid(newX, newY, matrix)) {
q.add(new pair(newX, newY ));
visited[newX][newY] = 1;
}
}
}
if(mp.containsKey(COUNT)){
mp.put(COUNT, mp.get(COUNT)+1);
}
else{
mp.put(COUNT, 1);
}
}
}
}
}
// Drivers Code
public static void main(String[] args)
{
// Given input array of 1s and 0s
int matrix[][]
= { { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };
// queries array
int queries[] = { 6, 1, 8, 2 };
// sizeof queries array
int N = queries.length;
// Count the frequency of each connected component
findComponentSize(matrix);
// Iterate over the given queries array and
// And answer the queries
for (int i = 0; i < N; i++)
System.out.print((mp.get(queries[i])!=null?mp.get(queries[i]):0)+ " ");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation for the above approach
n = 6
m = 6
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
# stores information about which cell
# are already visited in a particular BFS
visited = [[False for i in range(m)] for j in range(n)]
# Stores the final result grid
result = [[0 for i in range(m)] for j 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 1
def is_valid(x, y, matrix):
if (x < n and y < m and x >= 0 and y >= 0):
if (visited[x][y] == False and matrix[x][y] == 1):
return True
else:
return False
else:
return False
# Map to count the frequency of
# each connected component
mp = {}
# function to calculate the
# largest connected component
def findComponentSize(matrix):
# Iterate over every cell
for i in range(n):
for j in range(m):
if(visited[i][j]== False and matrix[i][j] == 1):
COUNT = 0
# Stores the indices of the matrix cells
q = []
# Mark the starting cell as visited
# and push it into the queue
q.append([i, j])
visited[i][j] = True
# Iterate while the queue
# is not empty
while (len(q)!=0):
p = q[0]
q = q[1:]
x = p[0]
y = p[1]
COUNT += 1
# Go to the adjacent cells
for i in range(4):
newX = x + dx[i]
newY = y + dy[i]
if (is_valid(newX, newY, matrix)):
q.append([newX, newY])
visited[newX][newY] = True
if COUNT in mp:
mp[COUNT] += 1
else:
mp[COUNT] = 1
# Drivers Code
if __name__ == '__main__':
# Given input array of 1s and 0s
matrix = [[1, 1, 1, 1, 1, 1],
[1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1],
[0, 0, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0]]
# queries array
queries = [6, 1, 8, 2]
# sizeof queries array
N = len(queries)
# Count the frequency of each connected component
findComponentSize(matrix)
# Iterate over the given queries array and
# And answer the queries
for i in range(N):
if queries[i] in mp:
print(mp[queries[i]],end = " ")
else:
print(0,end = " ")
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static int n = 6;
static int m = 6;
static int []dx = { 0, 1, -1, 0 };
static int []dy = { 1, 0, 0, -1 };
// stores information about which cell
// are already visited in a particular BFS
static int [,]visited = 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 1
static bool is_valid(int x, int y, int [,]matrix)
{
if (x < n && y < m && x >= 0 && y >= 0) {
if (visited[x,y] == 0
&& matrix[x,y] == 1)
return true;
else
return false;
}
else
return false;
}
// Map to count the frequency of
// each connected component
static Dictionary<int,int> mp = new Dictionary<int,int>();
// function to calculate the
// largest connected component
static void findComponentSize(int [,]matrix)
{
// Iterate over every cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i,j]==0 && matrix[i,j] == 1) {
COUNT = 0;
// Stores the indices of the matrix cells
List<pair> q = new List<pair>();
// Mark the starting cell as visited
// and push it into the queue
q.Add(new pair( i, j ));
visited[i,j] = 1;
// Iterate while the queue
// is not empty
while (q.Count>0) {
pair p = q[0];
q.RemoveAt();
int x = p.first, y = p.second;
COUNT++;
// Go to the adjacent cells
for (int k = 0; k < 4; k++) {
int newX = x + dx[k];
int newY = y + dy[k];
if (is_valid(newX, newY, matrix)) {
q.Add(new pair(newX, newY ));
visited[newX,newY] = 1;
}
}
}
if(mp.ContainsKey(COUNT)){
mp[COUNT] += 1;
}
else{
mp.Add(COUNT, 1);
}
}
}
}
}
// Drivers Code
public static void Main()
{
// Given input array of 1s and 0s
int [,]matrix
= new int[,]{ { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },
{ 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };
// queries array
int []queries = { 6, 1, 8, 2 };
// sizeof queries array
int N = queries.Length;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
visited[i,j] = 0;
}
}
// Count the frequency of each connected component
findComponentSize(matrix);
// Iterate over the given queries array and
// And answer the queries
for (int i = 0; i < N; i++)
if(mp.ContainsKey(queries[i])!=false)
Console.Write(mp[queries[i]] + " ");
}
}
// This code is contributed by 29AjayKumar
Producción:
1 2 1 0
Complejidad de tiempo: O(n*m)
Complejidad de espacio: O(n*m)
Publicación traducida automáticamente
Artículo escrito por ramandeep8421 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA