Cuadrado más grande en una array binaria con un máximo de K 1 para consultas múltiples

Dada una array binaria M donde cada elemento de la array será 0 o 1, la tarea es encontrar el cuadrado más grande que se puede formar con el centro (i, j) y que contiene como máximo K 1.

Entrada: M[][] = { 
{1, 0, 1, 0, 0} 
{1, 0, 1, 1, 1} 
{1, 1, 1, 1, 1} 
{1, 0, 0, 1 , 0}}, 
i = 1, j = 2, K = 9 
Salida:
Explicación: 
El cuadrado de longitud máxima con centro en (1, 2) 
que se puede formar tiene una longitud de 3 de (0, 1) a (2, 4)

Entrada: M[][] = { 
{ 1, 1, 1 }, 
{ 1, 1, 1 }, 
{ 1, 1, 1 }}, 
i = 1, j = 1, K = 9 
Salida: 3

Enfoque ingenuo: 
para cada consulta, considere todos los cuadrados con centro (i, j) y siga incrementando la longitud de los cuadrados desde 1 hasta su valor máximo posible hasta el cual la cuenta de 1 en el cuadrado es menor que K. El máximo posible el valor de la longitud del cuadrado será 2*MIN_DIST + 1 donde MIN_DIST es la distancia mínima del centro a los bordes de la array. Entonces, para una array R*C con centro (i, j),

MIN_DIST = min( i, j, R-i-1, C-j-1 ) 

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

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
  
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
  
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
void largestSquare(int matrix[][MAX],
             int R, int C, int q_i[],
            int q_j[], int K, int Q){
                  
    // Loop to solve for each query
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        int min_dist = min(min(i, j),
          min(R - i - 1, C - j - 1));
        int ans = -1;
        for (int k = 0; k <= min_dist;
                                 k++) {
            int count = 0;
            // Traversing the each sub
            // square and counting total
            for (int row = i - k; 
              row <= i + k; row++)
                for (int col = j - k;
                  col <= j + k; col++)
                    count += matrix[row][col];
              
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
              
            ans = 2 * k + 1;
        }
        cout << ans << "\n";
    }
}
  
// Driver Code
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i,
                          q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
class GFG{
      
static int MAX = 100;
  
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
static void largestSquare(int matrix[][], 
                          int R, int C, 
                          int q_i[], int q_j[], 
                          int K, int Q)
{
      
    // Loop to solve for each query
    for(int q = 0; q < Q; q++) 
    {
       int i = q_i[q];
       int j = q_j[q];
       int min_dist = Math.min(Math.min(i, j),
                      Math.min(R - i - 1, 
                               C - j - 1));
       int ans = -1;
       for(int k = 0; k <= min_dist; k++)
       {
          int count = 0;
            
          // Traversing the each sub
          // square and counting total
          for(int row = i - k; row <= i + k; row++)
             for(int col = j - k; col <= j + k; col++)
                count += matrix[row][col];
              
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
              
            ans = 2 * k + 1;
        }
          
        System.out.print(ans + "\n");
    }
}
  
// Driver Code
public static void main(String[] args)
{
    int matrix[][] = { { 1, 0, 1, 0, 0 },
                       { 1, 0, 1, 1, 1 },
                       { 1, 1, 1, 1, 1 },
                       { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
}
}
  
// This code is contributed by Amit Katiyar

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains at most K 1's 
  
MAX = 100
  
# Function to calculate the 
# largest square with atmost K 
# 1s for Q queries 
def largestSquare(matrix, R, C, q_i, q_j, K, Q): 
                  
    # Loop to solve for each query 
    for q in range(Q): 
        i = q_i[q] 
        j = q_j[q] 
        min_dist = min(min(i, j), 
                   min(R - i - 1, C - j - 1)) 
        ans = -1
        for k in range(min_dist + 1):
              
            count = 0
              
            # Traversing the each sub 
            # square and counting total 
            for row in range(i - k, i + k + 1): 
                for col in range(j - k, j + k + 1): 
                    count += matrix[row][col] 
              
            # Breaks when exceeds 
            # the maximum count 
            if count > K: 
                break
              
            ans = 2 * k + 1
        print(ans) 
          
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [ 1 ] 
q_j = [ 2 ] 
largestSquare(matrix, 4, 5, q_i, q_j, K, Q)
                          
# This code is contributed by divyamohan123                     
                     

C#

// C# implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
using System;
  
class GFG{
      
//static int MAX = 100;
  
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
static void largestSquare(int [,]matrix, 
                          int R, int C, 
                          int []q_i, int []q_j, 
                          int K, int Q)
{
      
    // Loop to solve for each query
    for(int q = 0; q < Q; q++) 
    {
       int i = q_i[q];
       int j = q_j[q];
       int min_dist = Math.Min(Math.Min(i, j), 
                               Math.Min(R - i - 1,
                                        C - j - 1));
       int ans = -1;
       for(int k = 0; k <= min_dist; k++)
       {
          int count = 0;
            
          // Traversing the each sub
          // square and counting total
          for(int row = i - k; row <= i + k; row++)
             for(int col = j - k; col <= j + k; col++)
                count += matrix[row, col];
                  
          // Breaks when exceeds
          // the maximum count
          if (count > K)
              break;
            
          ans = 2 * k + 1;
       }
       Console.Write(ans + "\n");
    }
}
  
// Driver Code
public static void Main(String[] args)
{
    int [,]matrix = { { 1, 0, 1, 0, 0 },
                      { 1, 0, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int []q_i = {1};
    int []q_j = {2};
      
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
}
}
  
// This code is contributed by Amit Katiyar

Javascript

<script>
  
// Javascript implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
  
var MAX = 100;
  
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
function largestSquare( matrix,
             R, C, q_i, q_j, K, Q){
                  
    // Loop to solve for each query
    for (var q = 0; q < Q; q++) {
        var i = q_i[q];
        var j = q_j[q];
        var min_dist = Math.min(Math.min(i, j),
          Math.min(R - i - 1, C - j - 1));
        var ans = -1;
        for (var k = 0; k <= min_dist;
                                 k++) {
            var count = 0;
            // Traversing the each sub
            // square and counting total
            for (var row = i - k; 
              row <= i + k; row++)
                for (var col = j - k;
                  col <= j + k; col++)
                    count += matrix[row][col];
              
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
              
            ans = 2 * k + 1;
        }
        document.write( ans + "<br>");
    }
}
  
// Driver Code
var matrix = [ [ 1, 0, 1, 0, 0 ],
                    [ 1, 0, 1, 1, 1 ],
                    [ 1, 1, 1, 1, 1 ],
                    [ 1, 0, 0, 1, 0 ] ];
var K = 9, Q = 1;
var q_i = [1 ];
var q_j = [2 ];
largestSquare(matrix, 4, 5, q_i,
                      q_j, K, Q);
  
// This code is contributed by famously.
</script>

Producción :

3

La complejidad temporal en el peor de los casos para la solución dada es O(Q*N*N*MIN_DIST) donde N es la longitud del cuadrado (que es un máximo de 2*MIN_DIST + 1).
 

Enfoque eficiente usando programación dinámica: 
la idea es usar la programación dinámica para contar el número de 1 en cada cuadrado y luego incrementar la longitud en 1 hasta el límite y finalmente verificar que el conteo de 1 sea menor que K o no. En caso afirmativo, actualice la respuesta.
Para calcular el número de 1 en una subarray de (x1, y1) a (x2, y2) usando:

Number of 1's = sumDP[x2][y2] - sumDP[x2][y1-1] -
                sumDP[x1-1][y2] + sumDP[x1-1][y1-1]

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

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
  
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
  
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
void largestSquare(int matrix[][MAX],
            int R, int C, int q_i[],
            int q_j[], int K, int Q){
      
    int countDP[R][C];
    memset(countDP, 0, sizeof(countDP));
  
    // Precomputing the countDP 
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for (int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0];
    for (int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                             matrix[0][j];
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                       countDP[i - 1][j] +
                       countDP[i][j - 1] -
                       countDP[i - 1][j - 1];
      
    // Loop to solve Queries
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        int min_dist = min(min(i, j), 
          min(R - i - 1, C - j - 1));
        int ans = -1;
        for (int k = 0; k <= min_dist;
                                  k++) {
            int x1 = i - k, x2 = i + k;
            int y1 = j - k, y2 = j + k;
              
            // Calculating the number
            // of 1s in the submatrix
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
  
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        cout << ans << "\n";
    }
}
  
// Driver Code
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
  
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i,
                          q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
import java.util.*;
  
class GFG{
      
static int MAX = 100;
  
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
static void largestSquare(int matrix[][], int R,
                          int C, int q_i[], 
                          int q_j[], int K,
                          int Q)
{
    int [][]countDP = new int[R][C];
  
    // Precomputing the countDP 
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for(int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0];
    for(int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
    for(int i = 1; i < R; i++)
        for(int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
      
    // Loop to solve Queries
    for(int q = 0; q < Q; q++)
    {
        int i = q_i[q];
        int j = q_j[q];
          
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        int min_dist = Math.min(Math.min(i, j), 
                       Math.min(R - i - 1, 
                                C - j - 1));
                                  
        int ans = -1;
        for(int k = 0; k <= min_dist; k++)
        {
            int x1 = i - k, x2 = i + k;
            int y1 = j - k, y2 = j + k;
              
            // Calculating the number
            // of 1s in the submatrix
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        System.out.print(ans + "\n");
    }
}
  
// Driver Code
public static void main(String[] args)
{
    int matrix[][] = { { 1, 0, 1, 0, 0 },
                       { 1, 0, 1, 1, 1 },
                       { 1, 1, 1, 1, 1 },
                       { 1, 0, 0, 1, 0 } };
  
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
      
    largestSquare(matrix, 4, 5, q_i,
                        q_j, K, Q);
}
}
  
// This code is contributed by gauravrajput1

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
  
# Function to find the largest 
# square in the matrix such 
# that it contains atmost K 1's 
def largestSquare(matrix, R, C, q_i, 
                     q_j, K, Q):
      
    countDP = [[0 for x in range(C)]
                  for x in range(R)] 
      
    # Precomputing the countDP 
    # prefix sum of the matrix 
    countDP[0][0] = matrix[0][0] 
      
    for i in range(1, R):
        countDP[i][0] = (countDP[i - 1][0] + 
                          matrix[i][0])
      
    for j in range(1, C):
        countDP[0][j] = (countDP[0][j - 1] + 
                          matrix[0][j])
      
    for i in range(1, R):
        for j in range(1, C):
            countDP[i][j] = (matrix[i][j] + 
                            countDP[i - 1][j] + 
                            countDP[i][j - 1] - 
                            countDP[i - 1][j - 1])
      
    # Loop to solve Queries 
    for q in range(0, Q):
        i = q_i[q]
        j = q_j[q]
          
        # Calculating the maximum 
        # possible distance of the 
        # centre from edge 
        min_dist = min(i, j, R - i - 1,
                             C - j - 1)
        ans = -1
        for k in range(0, min_dist + 1): 
            x1 = i - k
            x2 = i + k
            y1 = j - k
            y2 = j + k 
                  
            # Calculating the number 
            # of 1s in the submatrix 
            count = countDP[x2][y2]; 
              
            if (x1 > 0): 
                    count -= countDP[x1 - 1][y2]
            if (y1 > 0):
                    count -= countDP[x2][y1 - 1]
            if (x1 > 0 and y1 > 0):
                    count += countDP[x1 - 1][y1 - 1]
                  
            if (count > K):
                    break
                      
            ans = 2 * k + 1
              
        print(ans)
          
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [1] 
q_j = [2] 
  
largestSquare(matrix, 4, 5, q_i, q_j, K, Q) 
  
# This code is contributed by Stream_Cipher

C#

// C# implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
using System;
  
class GFG{ 
      
//static int MAX = 100; 
  
// Function to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int [,]matrix, int R, 
                          int C, int []q_i, 
                          int []q_j, int K, 
                          int Q) 
{ 
    int [,]countDP = new int[R, C]; 
  
    // Precomputing the countDP 
    // prefix sum of the matrix 
    countDP[0, 0] = matrix[0, 0]; 
    for(int i = 1; i < R; i++) 
        countDP[i, 0] = countDP[i - 1, 0] + 
                             matrix[i, 0];
                               
    for(int j = 1; j < C; j++) 
        countDP[0, j] = countDP[0, j - 1] + 
                         matrix[0, j]; 
                           
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i, j] = matrix[i, j] + 
                           countDP[i - 1, j] + 
                           countDP[i, j - 1] - 
                           countDP[i - 1, j - 1]; 
      
    // Loop to solve Queries 
    for(int q = 0; q < Q; q++) 
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
          
        // Calculating the maximum 
        // possible distance of the 
        // centre from edge 
        int min_dist = Math.Min(Math.Min(i, j), 
                       Math.Min(R - i - 1, 
                                C - j - 1)); 
                                  
        int ans = -1; 
        for(int k = 0; k <= min_dist; k++) 
        { 
            int x1 = i - k, x2 = i + k; 
            int y1 = j - k, y2 = j + k; 
              
            // Calculating the number 
            // of 1s in the submatrix 
            int count = countDP[x2, y2]; 
            if (x1 > 0) 
                count -= countDP[x1 - 1, y2]; 
            if (y1 > 0) 
                count -= countDP[x2, y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1, y1 - 1]; 
            if (count > K) 
                break; 
  
            ans = 2 * k + 1; 
        } 
        Console.Write(ans + "\n"); 
    } 
} 
  
// Driver Code 
public static void Main(String[] args) 
{ 
    int [,]matrix = { { 1, 0, 1, 0, 0 }, 
                      { 1, 0, 1, 1, 1 }, 
                      { 1, 1, 1, 1, 1 }, 
                      { 1, 0, 0, 1, 0 } }; 
  
    int K = 9, Q = 1; 
    int []q_i = { 1 }; 
    int []q_j = { 2 }; 
      
    largestSquare(matrix, 4, 5, q_i, 
                  q_j, K, Q); 
} 
}
  
// This code is contributed by princi singh

Javascript

<script>
  
// Javascript implementation to find the
// largest square in the matrix such
// that it contains atmost K 1's
let MAX = 100;
  
// Function to find the
// largest square in the matrix such
// that it contains atmost K 1's
function largestSquare(matrix, R, C, q_i, q_j, K, Q)
{
    let countDP = new Array(R);
    for(let i = 0; i < R; i++)
    {
        countDP[i] = new Array(C);
        for(let j = 0; j < C; j++)
            countDP[i][j] = 0;
    }
   
    // Precomputing the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for(let i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
    for(let j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
    for(let i = 1; i < R; i++)
        for(let j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
       
    // Loop to solve Queries
    for(let q = 0; q < Q; q++)
    {
        let i = q_i[q];
        let j = q_j[q];
           
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        let min_dist = Math.min(Math.min(i, j),
                       Math.min(R - i - 1,
                                C - j - 1));
                                   
        let ans = -1;
        for(let k = 0; k <= min_dist; k++)
        {
            let x1 = i - k, x2 = i + k;
            let y1 = j - k, y2 = j + k;
               
            // Calculating the number
            // of 1s in the submatrix
            let count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        document.write(ans + "<br>");
    }
}
  
// Driver Code
let matrix = [ [ 1, 0, 1, 0, 0 ],
               [ 1, 0, 1, 1, 1 ],
               [ 1, 1, 1, 1, 1 ],
               [ 1, 0, 0, 1, 0 ] ];
let  K = 9, Q = 1;
let q_i = [1];
let q_j = [2];
  
largestSquare(matrix, 4, 5, q_i,
              q_j, K, Q);
  
// This code is contributed by unknown2108
  
</script>

Producción :

3

La complejidad de tiempo del peor de los casos para la solución dada es O(R*C+ Q*MIN_DIST) donde R, C son las dimensiones de la array inicial.
 

Enfoque eficiente usando programación dinámica y búsqueda binaria: 
la idea es usar una búsqueda binaria para encontrar el cuadrado más grande en lugar de incrementar la longitud de un lado iterativamente y converger hacia el lado que da como máximo K 1.
El espacio de búsqueda para la búsqueda binaria será-

// Minimum possible answer will be
// the square with side 0
l = 0

// Maximum possible will be to include
// the whole square possible from (i, j)
r = min(min(i, j), 
        min(R - i - 1, C - i - 1))

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

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
  
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
  
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
void largestSquare(int matrix[][MAX], 
            int R, int C, int q_i[],
            int q_j[], int K, int Q){
      
    int countDP[R][C];
    memset(countDP, 0, sizeof(countDP));
  
    // Precomputation of the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for (int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
    for (int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                             matrix[0][j];
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                       countDP[i - 1][j] +
                       countDP[i][j - 1] -
                   countDP[i - 1][j - 1];
      
    // Loop to solve each query
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        int min_dist = min(min(i, j),
          min(R - i - 1, C - j - 1));
        int ans = -1, l = 0, u = min_dist;
          
        // Binary Search to the side which
        // have atmost in K 1's in square
        while (l <= u) {
            int mid = (l + u) / 2;
            int x1 = i - mid, x2 = i + mid;
            int y1 = j - mid, y2 = j + mid;
            // Count total number of 1s in
            // the sub square considered
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
              
            // If the count is less than or
            // equals to the maximum move
            // to right half
            if (count <= K) {
                ans = 2 * mid + 1;
                l = mid + 1;
            }
            else
                u = mid - 1;
        }
        cout << ans << "\n";
    }
}
  
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
  
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5,
                q_i, q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
import java.util.*; 
  
class GFG{
  
// Function to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int matrix[][], int R,
                          int C, int q_i[], 
                          int q_j[], int K, int Q)
{ 
    int countDP[][] = new int[R][C]; 
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            countDP[i][j] = 0; 
  
    // Precomputation of the countDP 
    // prefix sum of the matrix 
    countDP[0][0] = matrix[0][0]; 
      
    for(int i = 1; i < R; i++) 
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0]; 
      
    for(int j = 1; j < C; j++) 
        countDP[0][j] = countDP[0][j - 1] + 
                         matrix[0][j]; 
      
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i][j] = matrix[i][j] + 
                           countDP[i - 1][j] + 
                           countDP[i][j - 1] - 
                           countDP[i - 1][j - 1]; 
      
    // Loop to solve each query 
    for(int q = 0; q < Q; q++)
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
          
        int min_dist = Math.min(Math.min(i, j), 
                                Math.min(R - i - 1,
                                         C - j - 1)); 
                                           
        int ans = -1, l = 0, u = min_dist; 
          
        // Binary Search to the side which 
        // have atmost in K 1's in square 
        while (l <= u)
        { 
            int mid = (l + u) / 2; 
            int x1 = i - mid, x2 = i + mid; 
            int y1 = j - mid, y2 = j + mid; 
              
            // Count total number of 1s in 
            // the sub square considered 
            int count = countDP[x2][y2]; 
              
            if (x1 > 0) 
                count -= countDP[x1 - 1][y2]; 
            if (y1 > 0) 
                count -= countDP[x2][y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1][y1 - 1]; 
              
            // If the count is less than or 
            // equals to the maximum move 
            // to right half 
            if (count <= K) 
            { 
                ans = 2 * mid + 1; 
                l = mid + 1; 
            } 
            else
                u = mid - 1; 
        } 
        System.out.println(ans); 
    } 
} 
  
// Driver code
public static void main(String args[]) 
{ 
    int matrix[][] = { { 1, 0, 1, 0, 0 }, 
                       { 1, 0, 1, 1, 1 }, 
                       { 1, 1, 1, 1, 1 }, 
                       { 1, 0, 0, 1, 0 } }; 
  
    int K = 9, Q = 1; 
    int q_i[] = {1}; 
    int q_j[] = {2}; 
      
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q); 
} 
}
  
// This code is contributed by Stream_Cipher

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
  
# Function to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
def largestSquare(matrix, R, C, q_i, 
                     q_j, K, Q):
                           
    countDP = [[0 for x in range(C)]
                  for x in range(R)] 
      
    # Precomputing the countDP 
    # prefix sum of the matrix 
    countDP[0][0] = matrix[0][0] 
      
    for i in range(1, R):
        countDP[i][0] = (countDP[i - 1][0] +
                              matrix[i][0])
    for j in range(1, C):
        countDP[0][j] = (countDP[0][j - 1] +
                          matrix[0][j])
    for i in range(1, R):
        for j in range(1, C):
            countDP[i][j] = (matrix[i][j] + 
                            countDP[i - 1][j] + 
                            countDP[i][j - 1] - 
                            countDP[i - 1][j - 1])
      
    # Loop to solve Queries 
    for q in range(0,Q):
        i = q_i[q]
        j = q_j[q]
          
        # Calculating the maximum 
        # possible distance of the 
        # centre from edge 
        min_dist = min(i, j, R - i - 1, 
                             C - j - 1)
        ans = -1
        l = 0
        u = min_dist
          
        while (l <= u):
            mid = int((l + u) / 2) 
            x1 = i - mid
            x2 = i + mid 
            y1 = j - mid
            y2 = j + mid 
              
        # Count total number of 1s in 
        # the sub square considered 
            count = countDP[x2][y2]
              
            if (x1 > 0):
                    count -= countDP[x1 - 1][y2] 
            if (y1 > 0):
                    count -= countDP[x2][y1 - 1]
            if (x1 > 0 and y1 > 0): 
                    count += countDP[x1 - 1][y1 - 1]
              
        # If the count is less than or 
        # equals to the maximum move 
        # to right half 
            if (count <= K): 
                    ans = 2 * mid + 1
                    l = mid + 1
            else:
                u = mid - 1
                  
        print(ans)
          
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [1] 
q_j = [2] 
  
largestSquare(matrix, 4, 5, q_i, q_j, K, Q) 
  
# This code is contributed by Stream_Cipher

C#

// C# implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
using System.Collections.Generic; 
using System;
  
class GFG{
  
// Function to find the largest 
// square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int [,]matrix, int R,
                          int C, int []q_i, 
                          int []q_j, int K, int Q)
{ 
    int [,]countDP = new int[R, C]; 
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            countDP[i, j]=0; 
  
    // Precomputation of the countDP 
    // prefix sum of the matrix 
    countDP[0, 0] = matrix[0, 0]; 
    for(int i = 1; i < R; i++) 
        countDP[i, 0] = countDP[i - 1, 0] + 
                         matrix[i, 0]; 
                           
    for(int j = 1; j < C; j++) 
        countDP[0, j] = countDP[0, j - 1] + 
                         matrix[0, j]; 
                           
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i, j] = matrix[i, j] + 
                           countDP[i - 1, j] + 
                           countDP[i, j - 1] - 
                           countDP[i - 1, j - 1]; 
      
    // Loop to solve each query 
    for(int q = 0; q < Q; q++)
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
          
        int min_dist = Math.Min(Math.Min(i, j), 
                                Math.Min(R - i - 1,
                                         C - j - 1));
                                           
        int ans = -1, l = 0, u = min_dist; 
          
        // Binary Search to the side which 
        // have atmost in K 1's in square 
        while (l <= u) 
        { 
            int mid = (l + u) / 2; 
            int x1 = i - mid, x2 = i + mid; 
            int y1 = j - mid, y2 = j + mid; 
              
            // Count total number of 1s in 
            // the sub square considered 
            int count = countDP[x2, y2];
              
            if (x1 > 0) 
                count -= countDP[x1 - 1, y2]; 
            if (y1 > 0) 
                count -= countDP[x2, y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1, y1 - 1]; 
              
            // If the count is less than or 
            // equals to the maximum move 
            // to right half 
            if (count <= K) 
            { 
                ans = 2 * mid + 1; 
                l = mid + 1; 
            } 
            else
                u = mid - 1; 
        } 
        Console.WriteLine(ans); 
    } 
} 
  
// Driver code
public static void Main() 
{ 
    int [,]matrix = { { 1, 0, 1, 0, 0 }, 
                      { 1, 0, 1, 1, 1 }, 
                      { 1, 1, 1, 1, 1 }, 
                      { 1, 0, 0, 1, 0 } }; 
  
    int K = 9, Q = 1; 
    int []q_i = { 1 }; 
    int []q_j = { 2 }; 
      
    largestSquare(matrix, 4, 5, 
                     q_i, q_j, K, Q); 
} 
}
  
// This code is contributed by Stream_Cipher

Javascript

<script>
// Javascript implementation to find the
// largest square in the matrix such
// that it contains atmost K 1's
  
// Function to find the
// largest square in the matrix such
// that it contains atmost K 1's
function largestSquare(matrix,R,C,q_i,q_j,K,Q)
{
    let countDP = new Array(R);
    for(let i = 0; i < R; i++)
    {
        countDP[i]=new Array(C);
        for(let j = 0; j < C; j++)
            countDP[i][j] = 0;
     }
    // Precomputation of the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
       
    for(let i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
       
    for(let j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
       
    for(let i = 1; i < R; i++)
        for(let j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
       
    // Loop to solve each query
    for(let q = 0; q < Q; q++)
    {
        let i = q_i[q];
        let j = q_j[q];
           
        let min_dist = Math.min(Math.min(i, j),
                                Math.min(R - i - 1,
                                         C - j - 1));
                                            
        let ans = -1, l = 0, u = min_dist;
           
        // Binary Search to the side which
        // have atmost in K 1's in square
        while (l <= u)
        {
            let mid = Math.floor((l + u) / 2);
            let x1 = i - mid, x2 = i + mid;
            let y1 = j - mid, y2 = j + mid;
               
            // Count total number of 1s in
            // the sub square considered
            let count = countDP[x2][y2];
               
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
               
            // If the count is less than or
            // equals to the maximum move
            // to right half
            if (count <= K)
            {
                ans = 2 * mid + 1;
                l = mid + 1;
            }
            else
                u = mid - 1;
        }
        document.write(ans+"<br>");
    }
}
  
// Driver code
let matrix=[[ 1, 0, 1, 0, 0 ],
                       [ 1, 0, 1, 1, 1 ],
                       [ 1, 1, 1, 1, 1 ],
                       [ 1, 0, 0, 1, 0 ]];
  
let K = 9, Q = 1;
let q_i = [1];
let q_j = [2];
  
largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
  
  
// This code is contributed by patel2127
</script>

Producción: 

3

Complejidad de tiempo: O( R*C+ Q*log(MIN_DIST) ) 

Publicación traducida automáticamente

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