Consultas para contar los giros mínimos necesarios para llenar una subarray binaria solo con 0

Dada una array binaria mat[][] de tamaño M * N y Q consultas de la forma {pi, pj, qi, qj} , la tarea para cada consulta es contar el número de 0 s en la subarray de la celda ( pi, pj) a (qi, qj) .

Ejemplos:

Entrada: mat[][] = {{0, 1, 0, 1, 1, 1, 0}, {1, 0, 1, 1, 1, 0, 1}, {1, 1, 0, 0, 1, 1, 0}, {1, 1, 1, 1, 1, 0, 1}, {0, 0, 1, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 0, 1 }}, Q[] = {{0, 1, 3, 2}, {2, 2, 4, 5}, {4, 3, 5, 6}}
Salida: 3 4 2
Explicación: 
La subarray de los índices (0, 1) a (3, 2) contiene 3 0s. 
La subarray de los índices (2, 2) a (4, 5) contiene 4 0s. 
La subarray de los índices (4, 3) a (5, 6) contiene 2 0s.

Entrada: mat[][] = {{0, 1, 0}, {1, 0, 1}}, Q[] = {{0, 0, 2, 2}}
Salida: 3

Enfoque ingenuo: el enfoque más simple para resolver el problema es contar el número de 0 para cada consulta iterando la subarray e imprimir el recuento para cada consulta. 

Complejidad temporal: O(M*N*Q)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es preprocesar la array dada mat[][] . Cree una array de conteo, digamos prefixCnt[M][N] , tal que prefix_cnt[i][j] almacene el conteo de 0 s en la subarray dentro de los índices (0, 0) a (i, j) . Siga los pasos a continuación para calcular prefixCnt[][] :

  • Inicialice prefixCnt[i][j] con 1 si mat[i][j] es 0 . De lo contrario, inicialice con 0 .
  • Encuentre la suma del prefijo para cada fila y columna y actualice la array en consecuencia.

Una vez que se calcula el prefijo de array Cnt [] [] , el recuento de 0 en cualquier subarray se puede evaluar en tiempo O (1) . A continuación se muestra la expresión para contar los 0 en cada subarray desde (pi, pj) hasta (qi, qj) se puede calcular mediante:

cnt = prefijoCnt[qi][qj] – prefijoCnt[pi-1][qj] – prefijoCnt[qi][pj – 1] + prefijoCnt[pi – 1][pj – 1]

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define M 6
#define N 7
 
// Function to compute the matrix
// prefixCnt[M][N] from mat[M][N] such
// that prefixCnt[i][j] stores the
// count of 0's from (0, 0) to (i, j)
void preCompute(int mat[M][N],
                int prefixCnt[M][N])
{
    for (int i = 0; i < M; i++) {
 
        for (int j = 0; j < N; j++) {
 
            // Initialize prefixCnt[i][j]
            // with 1 if mat[i][j] is 0
            if (mat[i][j] == 0) {
                prefixCnt[i][j] = 1;
            }
 
            // Otherwise, assign with 0
            else {
                prefixCnt[i][j] = 0;
            }
        }
    }
 
    // Calculate prefix sum for each row
    for (int i = 0; i < M; i++)
        for (int j = 1; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i][j - 1];
 
    // Calculate prefix sum for each column
    for (int i = 1; i < M; i++)
        for (int j = 0; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i - 1][j];
}
 
// Function to compute count of 0's
// in submatrix from (pi, pj) to
// (qi, qj) from prefixCnt[M][N]
int countQuery(int prefixCnt[M][N],
               int pi, int pj,
               int qi, int qj)
{
    // Initialize that count of 0's
    // in the sub-matrix within
    // indices (0, 0) to (qi, qj)
    int cnt = prefixCnt[qi][qj];
 
    // Subtract count of 0's within
    // indices (0, 0) and (pi-1, qj)
    if (pi > 0)
        cnt -= prefixCnt[pi - 1][qj];
 
    // Subtract count of 0's within
    // indices (0, 0) and (qi, pj-1)
    if (pj > 0)
        cnt -= prefixCnt[qi][pj - 1];
 
    // Add prefixCnt[pi - 1][pj - 1]
    // because its value has been added
    // once but subtracted twice
    if (pi > 0 && pj > 0)
        cnt += prefixCnt[pi - 1][pj - 1];
 
    return cnt;
}
 
// Function to count the 0s in the
// each given submatrix
void count0s(int mat[M][N], int Q[][4],
             int sizeQ)
{
 
    // Stores the prefix sum of each
    // row and column
    int prefixCnt[M][N];
 
    // Compute matrix prefixCnt[][]
    preCompute(mat, prefixCnt);
 
    for (int i = 0; i < sizeQ; i++) {
 
        // Function Call for each query
        cout << countQuery(prefixCnt, Q[i][0],
                           Q[i][1], Q[i][2],
                           Q[i][3])
             << ' ';
    }
}
 
// Driver Code
int main()
{
    // Given matrix
    int mat[M][N] = {
        { 0, 1, 0, 1, 1, 1, 0 },
        { 1, 0, 1, 1, 1, 0, 1 },
        { 1, 1, 0, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 0, 1 },
        { 0, 0, 1, 0, 1, 1, 1 },
        { 1, 1, 0, 1, 1, 0, 1 }
    };
 
    int Q[][4] = { { 0, 1, 3, 2 },
                   { 2, 2, 4, 5 },
                   { 4, 3, 5, 6 } };
 
    int sizeQ = sizeof(Q) / sizeof(Q[0]);
 
    // Function Call
    count0s(mat, Q, sizeQ);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
     
final static int M = 6;
final static int N  = 7;
 
// Function to compute the matrix
// prefixCnt[M][N] from mat[M][N] such
// that prefixCnt[i][j] stores the
// count of 0's from (0, 0) to (i, j)
static void preCompute(int mat[][], int prefixCnt[][])
{
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
             
            // Initialize prefixCnt[i][j]
            // with 1 if mat[i][j] is 0
            if (mat[i][j] == 0)
            {
                prefixCnt[i][j] = 1;
            }
 
            // Otherwise, assign with 0
            else
            {
                prefixCnt[i][j] = 0;
            }
        }
    }
 
    // Calculate prefix sum for each row
    for(int i = 0; i < M; i++)
        for(int j = 1; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i][j - 1];
 
    // Calculate prefix sum for each column
    for(int i = 1; i < M; i++)
        for(int j = 0; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i - 1][j];
}
 
// Function to compute count of 0's
// in submatrix from (pi, pj) to
// (qi, qj) from prefixCnt[M][N]
static int countQuery(int prefixCnt[][],
                      int pi, int pj,
                      int qi, int qj)
{
     
    // Initialize that count of 0's
    // in the sub-matrix within
    // indices (0, 0) to (qi, qj)
    int cnt = prefixCnt[qi][qj];
     
    // Subtract count of 0's within
    // indices (0, 0) and (pi-1, qj)
    if (pi > 0)
        cnt -= prefixCnt[pi - 1][qj];
 
    // Subtract count of 0's within
    // indices (0, 0) and (qi, pj-1)
    if (pj > 0)
        cnt -= prefixCnt[qi][pj - 1];
 
    // Add prefixCnt[pi - 1][pj - 1]
    // because its value has been added;
    // once but subtracted twice
    if (pi > 0 && pj > 0)
        cnt += prefixCnt[pi - 1][pj - 1];
 
    return cnt;
}
 
// Function to count the 0s in the
// each given submatrix
static void count0s(int mat[][], int Q[][],
                    int sizeQ)
{
     
    // Stores the prefix sum of each
    // row and column
    int prefixCnt[][] = new int[M][N];
     
    // Compute matrix prefixCnt[][]
    preCompute(mat, prefixCnt);
 
    for(int i = 0; i < sizeQ; i++)
    {
         
        // Function Call for each query
        System.out.print(countQuery(prefixCnt, Q[i][0],
                                               Q[i][1],
                                               Q[i][2],
                                               Q[i][3]) + " ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given matrix
    int mat[][] = { { 0, 1, 0, 1, 1, 1, 0 },
                    { 1, 0, 1, 1, 1, 0, 1 },
                    { 1, 1, 0, 0, 1, 1, 0 },
                    { 1, 1, 1, 1, 1, 0, 1 },
                    { 0, 0, 1, 0, 1, 1, 1 },
                    { 1, 1, 0, 1, 1, 0, 1 } };
 
    int Q[][] = { { 0, 1, 3, 2 },
                  { 2, 2, 4, 5 },
                  { 4, 3, 5, 6 } };
 
    int sizeQ = Q.length;
 
    // Function Call
    count0s(mat, Q, sizeQ);
}
}
 
// This code is contributed by AnkThon

Python3

# Python3 program for the above approach
 
M = 6
N = 7
 
# Function to compute the matrix
# prefixCnt[M][N] from mat[M][N] such
# that prefixCnt[i][j] stores the
# count of 0's from (0, 0) to (i, j)
def preCompute(mat, prefixCnt):
    for i in range(M):
 
        for j in range(N):
 
            # Initialize prefixCnt[i][j]
            # with 1 if mat[i][j] is 0
            if (mat[i][j] == 0):
                prefixCnt[i][j] = 1
             
            # Otherwise, assign with 0
            else:
                prefixCnt[i][j] = 0
 
    # Calculate prefix sum for each row
    for i in range(M):
        for j in range(1, N):
            prefixCnt[i][j] += prefixCnt[i][j - 1]
 
    # Calculate prefix sum for each column
    for i in range(1, M):
        for j in range(N):
            prefixCnt[i][j] += prefixCnt[i - 1][j]
    return prefixCnt
 
# Function to compute count of 0's
# in submatrix from (pi, pj) to
# (qi, qj) from prefixCnt[M][N]
def countQuery(prefixCnt, pi, pj, qi, qj):
     
    # Initialize that count of 0's
    # in the sub-matrix within
    # indices (0, 0) to (qi, qj)
    cnt = prefixCnt[qi][qj]
 
    # Subtract count of 0's within
    # indices (0, 0) and (pi-1, qj)
    if (pi > 0):
        cnt -= prefixCnt[pi - 1][qj]
 
    # Subtract count of 0's within
    # indices (0, 0) and (qi, pj-1)
    if (pj > 0):
        cnt -= prefixCnt[qi][pj - 1]
 
    # Add prefixCnt[pi - 1][pj - 1]
    # because its value has been added
    # once but subtracted twice
    if (pi > 0 and pj > 0):
        cnt += prefixCnt[pi - 1][pj - 1]
 
    return cnt
 
# Function to count the 0s in the
# each given submatrix
def count0s(mat, Q, sizeQ):
 
    # Stores the prefix sum of each
    # row and column
    prefixCnt = [[ 0 for i in range(N)] for i in range(M)]
 
    # Compute matrix prefixCnt[][]
    prefixCnt = preCompute(mat, prefixCnt)
 
    for i in range(sizeQ):
 
        # Function Call for each query
        print(countQuery(prefixCnt, Q[i][0], Q[i][1], Q[i][2], Q[i][3]), end=" ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given matrix
    mat = [[ 0, 1, 0, 1, 1, 1, 0 ],
        [ 1, 0, 1, 1, 1, 0, 1 ],
        [ 1, 1, 0, 0, 1, 1, 0 ],
        [ 1, 1, 1, 1, 1, 0, 1 ],
        [ 0, 0, 1, 0, 1, 1, 1 ],
        [ 1, 1, 0, 1, 1, 0, 1 ] ]
 
    Q= [ [ 0, 1, 3, 2 ],
        [ 2, 2, 4, 5 ],
        [ 4, 3, 5, 6 ] ]
 
    sizeQ = len(Q)
 
    # Function Call
    count0s(mat, Q, sizeQ)
 
    # This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
     
static int M = 6;
static int N  = 7;
 
// Function to compute the matrix
// prefixCnt[M][N] from mat[M][N] such
// that prefixCnt[i][j] stores the
// count of 0's from (0, 0) to (i, j)
static void preCompute(int [,]mat, int [,]prefixCnt)
{
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
             
            // Initialize prefixCnt[i][j]
            // with 1 if mat[i,j] is 0
            if (mat[i, j] == 0)
            {
                prefixCnt[i, j] = 1;
            }
 
            // Otherwise, assign with 0
            else
            {
                prefixCnt[i, j] = 0;
            }
        }
    }
 
    // Calculate prefix sum for each row
    for(int i = 0; i < M; i++)
        for(int j = 1; j < N; j++)
            prefixCnt[i, j] += prefixCnt[i, j - 1];
 
    // Calculate prefix sum for each column
    for(int i = 1; i < M; i++)
        for(int j = 0; j < N; j++)
            prefixCnt[i, j] += prefixCnt[i - 1, j];
}
 
// Function to compute count of 0's
// in submatrix from (pi, pj) to
// (qi, qj) from prefixCnt[M][N]
static int countQuery(int [,]prefixCnt,
                      int pi, int pj,
                      int qi, int qj)
{
     
    // Initialize that count of 0's
    // in the sub-matrix within
    // indices (0, 0) to (qi, qj)
    int cnt = prefixCnt[qi, qj];
     
    // Subtract count of 0's within
    // indices (0, 0) and (pi-1, qj)
    if (pi > 0)
        cnt -= prefixCnt[pi - 1, qj];
 
    // Subtract count of 0's within
    // indices (0, 0) and (qi, pj-1)
    if (pj > 0)
        cnt -= prefixCnt[qi, pj - 1];
 
    // Add prefixCnt[pi - 1][pj - 1]
    // because its value has been added;
    // once but subtracted twice
    if (pi > 0 && pj > 0)
        cnt += prefixCnt[pi - 1, pj - 1];
 
    return cnt;
}
 
// Function to count the 0s in the
// each given submatrix
static void count0s(int [,]mat, int [,]Q,
                    int sizeQ)
{
     
    // Stores the prefix sum of each
    // row and column
    int [,]prefixCnt = new int[M, N];
     
    // Compute matrix prefixCnt[,]
    preCompute(mat, prefixCnt);
 
    for(int i = 0; i < sizeQ; i++)
    {
         
        // Function Call for each query
        Console.Write(countQuery(prefixCnt, Q[i, 0],
                                               Q[i, 1],
                                               Q[i, 2],
                                               Q[i, 3]) + " ");
    }
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given matrix
    int [,]mat = { { 0, 1, 0, 1, 1, 1, 0 },
                    { 1, 0, 1, 1, 1, 0, 1 },
                    { 1, 1, 0, 0, 1, 1, 0 },
                    { 1, 1, 1, 1, 1, 0, 1 },
                    { 0, 0, 1, 0, 1, 1, 1 },
                    { 1, 1, 0, 1, 1, 0, 1 } };
 
    int [,]Q = { { 0, 1, 3, 2 },
                  { 2, 2, 4, 5 },
                  { 4, 3, 5, 6 } };
 
    int sizeQ = Q.GetLength(0);
 
    // Function Call
    count0s(mat, Q, sizeQ);
}
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
// javascript program of the above approach
 
let M = 6;
let N  = 7;
 
// Function to compute the matrix
// prefixCnt[M][N] from mat[M][N] such
// that prefixCnt[i][j] stores the
// count of 0's from (0, 0) to (i, j)
function preCompute(mat, prefixCnt)
{
    for(let i = 0; i < M; i++)
    {
        for(let j = 0; j < N; j++)
        {
             
            // Initialize prefixCnt[i][j]
            // with 1 if mat[i][j] is 0
            if (mat[i][j] == 0)
            {
                prefixCnt[i][j] = 1;
            }
 
            // Otherwise, assign with 0
            else
            {
                prefixCnt[i][j] = 0;
            }
        }
    }
 
    // Calculate prefix sum for each row
    for(let i = 0; i < M; i++)
        for(let j = 1; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i][j - 1];
 
    // Calculate prefix sum for each column
    for(let i = 1; i < M; i++)
        for(let j = 0; j < N; j++)
            prefixCnt[i][j] += prefixCnt[i - 1][j];
}
 
// Function to compute count of 0's
// in submatrix from (pi, pj) to
// (qi, qj) from prefixCnt[M][N]
function countQuery(prefixCnt,
                      pi, pj,
                      qi, qj)
{
     
    // Initialize that count of 0's
    // in the sub-matrix within
    // indices (0, 0) to (qi, qj)
    let cnt = prefixCnt[qi][qj];
     
    // Subtract count of 0's within
    // indices (0, 0) and (pi-1, qj)
    if (pi > 0)
        cnt -= prefixCnt[pi - 1][qj];
 
    // Subtract count of 0's within
    // indices (0, 0) and (qi, pj-1)
    if (pj > 0)
        cnt -= prefixCnt[qi][pj - 1];
 
    // Add prefixCnt[pi - 1][pj - 1]
    // because its value has been added;
    // once but subtracted twice
    if (pi > 0 && pj > 0)
        cnt += prefixCnt[pi - 1][pj - 1];
 
    return cnt;
}
 
// Function to count the 0s in the
// each given submatrix
function count0s(mat, Q,
                    sizeQ)
{
     
    // Stores the prefix sum of each
    // row and column
    let prefixCnt = new Array(M);
     
    // Loop to create 2D array using 1D array
    for (var i = 0; i < prefixCnt.length; i++) {
        prefixCnt[i] = new Array(2);
    }
     
    // Compute matrix prefixCnt[][]
    preCompute(mat, prefixCnt);
 
    for(let i = 0; i < sizeQ; i++)
    {
         
        // Function Call for each query
        document.write(countQuery(prefixCnt, Q[i][0],
                                               Q[i][1],
                                               Q[i][2],
                                               Q[i][3]) + " ");
    }
}
 
    // Driver Code
     
     // Given matrix
    let mat = [[ 0, 1, 0, 1, 1, 1, 0 ],
                    [ 1, 0, 1, 1, 1, 0, 1 ],
                    [ 1, 1, 0, 0, 1, 1, 0 ],
                    [ 1, 1, 1, 1, 1, 0, 1 ],
                    [ 0, 0, 1, 0, 1, 1, 1 ],
                    [ 1, 1, 0, 1, 1, 0, 1 ]];
 
    let Q = [[ 0, 1, 3, 2 ],
                  [ 2, 2, 4, 5 ],
                  [ 4, 3, 5, 6 ]];
 
    let sizeQ = Q.length;
 
    // Function Call
    count0s(mat, Q, sizeQ);
 
// This code is contributed by target_2.
</script>
Producción: 

3 4 2

 

Complejidad temporal: O(M*N + Q)
Espacio auxiliar: O(M*N)

Publicación traducida automáticamente

Artículo escrito por sunidhichandra27 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 *