Consultas para encontrar el recuento de celdas no vacías conectadas en una array con actualizaciones

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)

Publicación traducida automáticamente

Artículo escrito por manoj_n y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *