Dada una array booleana mat[][] que consta de N filas y M columnas, inicialmente rellenas con 0 (celdas vacías), un número entero K y consultas Q[][] del tipo {X, Y}, la tarea es para reemplazar mat[X][Y] = 1 (celdas no vacías) y contar el número de celdas no vacías conectadas de la array dada.
Ejemplos:
Entrada: N = 3, M = 3, K = 4, Q[][] = {{0, 0}, {1, 1}, {1, 0}, {1, 2}}
Salida: 1 2 1 1
Explicación:
Inicialmente, mat[][] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}
Consulta 1: mat[][] = {{1, 0 , 0}, {0, 0, 0}, {0, 0, 0}}, Recuento = 1
Consulta 1: mat[][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 0}}, Recuento = 2
Consulta 1: mat[][] = {{1, 0, 0}, {1, 1, 0}, {0, 0, 0}}, Recuento = 1
Consulta 1: mat[][] = {{1, 0, 0}, {1, 1, 1}, {0, 0, 0}}, Count = 1
Entrada: N = 2, M = 2, K = 2, Q[][] = {{0, 0}, {0, 1}}
Salida: 1 1
Enfoque:
el problema se puede resolver utilizando la estructura de datos de conjuntos disjuntos . Siga los pasos a continuación para resolver el problema:
- Dado que, inicialmente, no hay 1 en la array, contar = 0 .
- Transforme el problema de dos dimensiones en el clásico Union-find , realizando un índice de mapeo lineal = X * M + Y , donde M es la longitud de la columna.
- Después de establecer un índice en cada consulta, incremente el recuento .
- Si una celda no vacía está presente en cualquiera de las 4 celdas adyacentes:
- Realice la operación de unión para el índice actual y la celda adyacente (conectando dos conjuntos).
- Disminuye el conteo a medida que se conectan dos conjuntos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Count of connected cells
int ctr = 0;
// Function to return the representative
// of the Set to which x belongs
int find(vector<int>& parent, int x)
{
// If x is parent of itself
if (parent[x] == x)
// x is representative
// of the Set
return x;
// Otherwise
parent[x] = find(parent, parent[x]);
// Path Compression
return parent[x];
}
// Unites the set that includes
// x and the set that includes y
void setUnion(vector<int>& parent,
vector<int>& rank, int x, int y)
{
// Find the representatives(or the
// root nodes) for x an y
int parentx = find(parent, x);
int parenty = find(parent, y);
// If both are in the same set
if (parenty == parentx)
return;
// Decrement count
ctr--;
// If x's rank is less than y's rank
if (rank[parentx] < rank[parenty]) {
parent[parentx] = parenty;
}
// Otherwise
else if (rank[parentx] > rank[parenty]) {
parent[parenty] = parentx;
}
else {
// Then move x under y (doesn't matter
// which one goes where)
parent[parentx] = parenty;
// And increment the result tree's
// rank by 1
rank[parenty]++;
}
}
// Function to count the number of
// connected cells in the matrix
vector<int> solve(int n, int m,
vector<pair<int, int> >& query)
{
// Store result for queries
vector<int> result(query.size());
// Store representative of
// each element
vector<int> parent(n * m);
// Initially, all elements
// are in their own set
for (int i = 0; i < n * m; i++)
parent[i] = i;
// Stores the rank(depth) of each node
vector<int> rank(n * m, 1);
vector<bool> grid(n * m, 0);
for (int i = 0; i < query.size(); i++) {
int x = query[i].first;
int y = query[i].second;
// If the grid[x*m + y] is already
// set, store the result
if (grid[m * x + y] == 1) {
result[i] = ctr;
continue;
}
// Set grid[x*m + y] to 1
grid[m * x + y] = 1;
// Increment count.
ctr++;
// Check for all adjacent cells
// to do a Union with neighbour's
// set if neighbour is also 1
if (x > 0 and grid[m * (x - 1) + y] == 1)
setUnion(parent, rank,
m * x + y, m * (x - 1) + y);
if (y > 0 and grid[m * (x) + y - 1] == 1)
setUnion(parent, rank,
m * x + y, m * (x) + y - 1);
if (x < n - 1 and grid[m * (x + 1) + y] == 1)
setUnion(parent, rank,
m * x + y, m * (x + 1) + y);
if (y < m - 1 and grid[m * (x) + y + 1] == 1)
setUnion(parent, rank,
m * x + y, m * (x) + y + 1);
// Store result.
result[i] = ctr;
}
return result;
}
// Driver Code
int main()
{
int N = 3, M = 3, K = 4;
vector<pair<int, int> > query
= { { 0, 0 },
{ 1, 1 },
{ 1, 0 },
{ 1, 2 } };
vector<int> result = solve(N, M, query);
for (int i = 0; i < K; i++)
cout << result[i] << " ";
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Count of connected cells
static int ctr = 0;
// Function to return the representative
// of the Set to which x belongs
static int find(int []parent, int x)
{
// If x is parent of itself
if (parent[x] == x)
// x is representative
// of the Set
return x;
// Otherwise
parent[x] = find(parent, parent[x]);
// Path Compression
return parent[x];
}
// Unites the set that includes
// x and the set that includes y
static void setUnion(int[] parent,
int[] rank, int x, int y)
{
// Find the representatives(or the
// root nodes) for x an y
int parentx = find(parent, x);
int parenty = find(parent, y);
// If both are in the same set
if (parenty == parentx)
return;
// Decrement count
ctr--;
// If x's rank is less than y's rank
if (rank[parentx] < rank[parenty])
{
parent[parentx] = parenty;
}
// Otherwise
else if (rank[parentx] > rank[parenty])
{
parent[parenty] = parentx;
}
else
{
// Then move x under y (doesn't matter
// which one goes where)
parent[parentx] = parenty;
// And increment the result tree's
// rank by 1
rank[parenty]++;
}
}
// Function to count the number of
// connected cells in the matrix
static int [] solve(int n, int m,
int [][]query)
{
// Store result for queries
int []result = new int[query.length];
// Store representative of
// each element
int []parent = new int[n * m];
// Initially, all elements
// are in their own set
for(int i = 0; i < n * m; i++)
parent[i] = i;
// Stores the rank(depth) of each node
int []rank = new int[n * m];
Arrays.fill(rank, 1);
boolean []grid = new boolean[n * m];
for(int i = 0; i < query.length; i++)
{
int x = query[i][0];
int y = query[i][1];
// If the grid[x*m + y] is already
// set, store the result
if (grid[m * x + y] == true)
{
result[i] = ctr;
continue;
}
// Set grid[x*m + y] to 1
grid[m * x + y] = true;
// Increment count.
ctr++;
// Check for all adjacent cells
// to do a Union with neighbour's
// set if neighbour is also 1
if (x > 0 && grid[m * (x - 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x - 1) + y);
if (y > 0 && grid[m * (x) + y - 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y - 1);
if (x < n - 1 && grid[m * (x + 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x + 1) + y);
if (y < m - 1 && grid[m * (x) + y + 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y + 1);
// Store result.
result[i] = ctr;
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int N = 3, M = 3, K = 4;
int [][]query = { { 0, 0 },
{ 1, 1 },
{ 1, 0 },
{ 1, 2 } };
int[] result = solve(N, M, query);
for(int i = 0; i < K; i++)
System.out.print(result[i] + " ");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python 3 program to implement # the above approach # Count of connected cells ctr = 0 # Function to return the # representative of the Set # to which x belongs def find(parent, x): # If x is parent of itself if (parent[x] == x): # x is representative # of the Set return x # Otherwise parent[x] = find(parent, parent[x]) # Path Compression return parent[x] # Unites the set that # includes x and the # set that includes y def setUnion(parent, rank, x, y): global ctr # Find the representatives # (or the root nodes) for x an y parentx = find(parent, x) parenty = find(parent, y) # If both are in the same set if (parenty == parentx): return # Decrement count ctr -= 1 # If x's rank is less than y's rank if (rank[parentx] < rank[parenty]): parent[parentx] = parenty # Otherwise elif (rank[parentx] > rank[parenty]): parent[parenty] = parentx else: # Then move x under y # (doesn't matter which # one goes where) parent[parentx] = parenty # And increment the result # tree's rank by 1 rank[parenty] += 1 # Function to count the number of # connected cells in the matrix def solve(n, m, query): global ctr # Store result for queries result = [0] * len(query) # Store representative of # each element parent = [0] * (n * m) # Initially, all elements # are in their own set for i in range (n * m): parent[i] = i # Stores the rank(depth) # of each node rank = [1] * (n * m) grid = [0] * (n * m) for i in range (len( query)): x = query[i][0] y = query[i][1] # If the grid[x*m + y] is already # set, store the result if (grid[m * x + y] == 1): result[i] = ctr continue # Set grid[x*m + y] to 1 grid[m * x + y] = 1 # Increment count. ctr += 1 # Check for all adjacent cells # to do a Union with neighbour's # set if neighbour is also 1 if (x > 0 and grid[m * (x - 1) + y] == 1): setUnion(parent, rank, m * x + y, m * (x - 1) + y) if (y > 0 and grid[m * (x) + y - 1] == 1): setUnion(parent, rank, m * x + y, m * (x) + y - 1) if (x < n - 1 and grid[m * (x + 1) + y] == 1): setUnion(parent, rank, m * x + y, m * (x + 1) + y) if (y < m - 1 and grid[m * (x) + y + 1] == 1): setUnion(parent, rank, m * x + y, m * (x) + y + 1) # Store result. result[i] = ctr return result # Driver Code if __name__ == "__main__": N = 3 M = 3 K = 4 query = [[0, 0], [1, 1], [1, 0], [1, 2]] result = solve(N, M, query) for i in range (K): print (result[i], end = " ") # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Count of connected cells
static int ctr = 0;
// Function to return the representative
// of the Set to which x belongs
static int find(int []parent, int x)
{
// If x is parent of itself
if (parent[x] == x)
// x is representative
// of the Set
return x;
// Otherwise
parent[x] = find(parent, parent[x]);
// Path Compression
return parent[x];
}
// Unites the set that includes
// x and the set that includes y
static void setUnion(int[] parent,
int[] rank,
int x, int y)
{
// Find the representatives(or the
// root nodes) for x an y
int parentx = find(parent, x);
int parenty = find(parent, y);
// If both are in the same set
if (parenty == parentx)
return;
// Decrement count
ctr--;
// If x's rank is less than y's rank
if (rank[parentx] < rank[parenty])
{
parent[parentx] = parenty;
}
// Otherwise
else if (rank[parentx] > rank[parenty])
{
parent[parenty] = parentx;
}
else
{
// Then move x under y (doesn't matter
// which one goes where)
parent[parentx] = parenty;
// And increment the result tree's
// rank by 1
rank[parenty]++;
}
}
// Function to count the number of
// connected cells in the matrix
static int [] solve(int n, int m,
int [,]query)
{
// Store result for queries
int []result = new int[query.Length];
// Store representative of
// each element
int []parent = new int[n * m];
// Initially, all elements
// are in their own set
for(int i = 0; i < n * m; i++)
parent[i] = i;
// Stores the rank(depth) of each node
int []rank = new int[n * m];
for(int i = 0; i < rank.Length; i++)
rank[i] = 1;
bool []grid = new bool[n * m];
for(int i = 0; i < query.GetLength(0); i++)
{
int x = query[i, 0];
int y = query[i, 1];
// If the grid[x*m + y] is already
// set, store the result
if (grid[m * x + y] == true)
{
result[i] = ctr;
continue;
}
// Set grid[x*m + y] to 1
grid[m * x + y] = true;
// Increment count.
ctr++;
// Check for all adjacent cells
// to do a Union with neighbour's
// set if neighbour is also 1
if (x > 0 && grid[m * (x - 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x - 1) + y);
if (y > 0 && grid[m * (x) + y - 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y - 1);
if (x < n - 1 && grid[m * (x + 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x + 1) + y);
if (y < m - 1 && grid[m * (x) + y + 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y + 1);
// Store result.
result[i] = ctr;
}
return result;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3, M = 3, K = 4;
int [,]query = {{ 0, 0 }, { 1, 1 },
{ 1, 0 }, { 1, 2 }};
int[] result = solve(N, M, query);
for(int i = 0; i < K; i++)
Console.Write(result[i] + " ");
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to implement
// the above approach
// Count of connected cells
let ctr = 0;
// Function to return the representative
// of the Set to which x belongs
function find(parent,x)
{
// If x is parent of itself
if (parent[x] == x)
// x is representative
// of the Set
return x;
// Otherwise
parent[x] = find(parent, parent[x]);
// Path Compression
return parent[x];
}
// Unites the set that includes
// x and the set that includes y
function setUnion(parent,rank,x,y)
{
// Find the representatives(or the
// root nodes) for x an y
let parentx = find(parent, x);
let parenty = find(parent, y);
// If both are in the same set
if (parenty == parentx)
return;
// Decrement count
ctr--;
// If x's rank is less than y's rank
if (rank[parentx] < rank[parenty])
{
parent[parentx] = parenty;
}
// Otherwise
else if (rank[parentx] > rank[parenty])
{
parent[parenty] = parentx;
}
else
{
// Then move x under y (doesn't matter
// which one goes where)
parent[parentx] = parenty;
// And increment the result tree's
// rank by 1
rank[parenty]++;
}
}
// Function to count the number of
// connected cells in the matrix
function solve(n,m,query)
{
// Store result for queries
let result = new Array(query.length);
// Store representative of
// each element
let parent = new Array(n * m);
// Initially, all elements
// are in their own set
for(let i = 0; i < n * m; i++)
parent[i] = i;
// Stores the rank(depth) of each node
let rank = new Array(n * m);
let grid = new Array(n * m);
for(let i=0;i<(n*m);i++)
{
rank[i]=0;
grid[i]=false;
}
for(let i = 0; i < query.length; i++)
{
let x = query[i][0];
let y = query[i][1];
// If the grid[x*m + y] is already
// set, store the result
if (grid[m * x + y] == true)
{
result[i] = ctr;
continue;
}
// Set grid[x*m + y] to 1
grid[m * x + y] = true;
// Increment count.
ctr++;
// Check for all adjacent cells
// to do a Union with neighbour's
// set if neighbour is also 1
if (x > 0 && grid[m * (x - 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x - 1) + y);
if (y > 0 && grid[m * (x) + y - 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y - 1);
if (x < n - 1 && grid[m * (x + 1) + y] == true)
setUnion(parent, rank,
m * x + y, m * (x + 1) + y);
if (y < m - 1 && grid[m * (x) + y + 1] == true)
setUnion(parent, rank,
m * x + y, m * (x) + y + 1);
// Store result.
result[i] = ctr;
}
return result;
}
// Driver Code
let N = 3, M = 3, K = 4;
let query = [[ 0, 0 ],
[ 1, 1 ],
[ 1, 0 ],
[ 1, 2 ]];
let result = solve(N, M, query);
for(let i = 0; i < K; i++)
document.write(result[i] + " ");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 2 1 1
Complejidad de tiempo: O(N * M * sizeof(Q))
Espacio auxiliar: O(N*M)