Dados dos números enteros L y W que representan las dimensiones de una cuadrícula, y dos arrays X[] e Y[] de longitud N que indican el número de torres presentes en la cuadrícula en las posiciones (X[i], Y[i]), donde (0 <= yo <= N – 1). La tarea es encontrar el área ilimitada más grande en el campo que no esté defendida por las torres.
Ejemplos:
Entrada: L = 15, W = 8, N = 3 X[] = {3, 11, 8} Y[] = {8, 2, 6} Salida: 12 Explicación: Las coordenadas de las torres son
( 3
,
8 ), (11, 2) y (8, 6).
Observe que el área más grande de la cuadrícula que no está protegida por ninguna de las torres está dentro de las celdas (4, 3), (7, 3), (7, 5) y (4, 5). Por lo tanto, el área de esa parte es 12.Entrada: L = 3, W = 3, N = 1 X[] = {1} Y[] = {1}
Salida: 4
Explicación:
observe que el área más grande de la cuadrícula que no está protegida por ninguna de las torres es 4.
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- Inicialice una array de dimensiones L * W con 0s.
- Atraviese X[] e Y[], y para cada (X[i], Y[i]) , marque todas las celdas en la fila X[i] y la columna Y[i] con 1, para indicar que están protegidas por la torre en (X[i], Y[i]) .
- Luego recorra la array y para cada celda, y encuentre la subarray más grande que se deja sin protección, es decir, la subarray más grande que consta de ceros. Imprime el área correspondiente.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la siguiente técnica Greedy :
- Ordene ambas listas de coordenadas X[] e Y[] .
- Calcule los espacios vacíos entre las coordenadas x, es decir, dX[] = {X 1 , X 2 – X 1 , …., X N – X (N-1) , (L+1) – X N } . Del mismo modo, calcule los espacios entre las coordenadas y, dY[] = {Y 1 , Y 2 – Y 1 , …., Y N – Y (N-1) , (W + 1) – Y N } .
- Atraviese dX[] y dY[] y calcule sus respectivos máximos.
- Calcule el producto de sus máximos e imprímalo como el área ilimitada más larga requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <algorithm>
#include <iostream>
using namespace std;
// Function to calculate the largest
// area unguarded by towers
void maxArea(int point_x[], int point_y[], int n,
int length, int width)
{
// Sort the x-coordinates of the list
sort(point_x, point_x + n);
// Sort the y-coordinates of the list
sort(point_y, point_y + n);
// dx --> maximum uncovered
// tiles in x coordinates
int dx = point_x[0];
// dy --> maximum uncovered
// tiles in y coordinates
int dy = point_y[0];
// Calculate the maximum uncovered
// distances for both x and y coordinates
for (int i = 1; i < n; i++) {
dx = max(dx, point_x[i]
- point_x[i - 1]);
dy = max(dy, point_y[i]
- point_y[i - 1]);
}
dx = max(dx, (length + 1)
- point_x[n - 1]);
dy = max(dy, (width + 1)
- point_y[n - 1]);
// Largest unguarded area is
// max(dx)-1 * max(dy)-1
cout << (dx - 1) * (dy - 1);
cout << endl;
}
// Driver Code
int main()
{
// Length and width of the grid
int length = 15, width = 8;
// No of guard towers
int n = 3;
// Array to store the x and
// y coordinates
int point_x[] = { 3, 11, 8 };
int point_y[] = { 8, 2, 6 };
// Function call
maxArea(point_x, point_y,
n, length, width);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate the largest
// area unguarded by towers
static void maxArea(int[] point_x, int[] point_y,
int n, int length, int width)
{
// Sort the x-coordinates of the list
Arrays.sort(point_x);
// Sort the y-coordinates of the list
Arrays.sort(point_y);
// dx --> maximum uncovered
// tiles in x coordinates
int dx = point_x[0];
// dy --> maximum uncovered
// tiles in y coordinates
int dy = point_y[0];
// Calculate the maximum uncovered
// distances for both x and y coordinates
for(int i = 1; i < n; i++)
{
dx = Math.max(dx, point_x[i] -
point_x[i - 1]);
dy = Math.max(dy, point_y[i] -
point_y[i - 1]);
}
dx = Math.max(dx, (length + 1) -
point_x[n - 1]);
dy = Math.max(dy, (width + 1) -
point_y[n - 1]);
// Largest unguarded area is
// max(dx)-1 * max(dy)-1
System.out.println((dx - 1) * (dy - 1));
}
// Driver Code
public static void main(String[] args)
{
// Length and width of the grid
int length = 15, width = 8;
// No of guard towers
int n = 3;
// Array to store the x and
// y coordinates
int point_x[] = { 3, 11, 8 };
int point_y[] = { 8, 2, 6 };
// Function call
maxArea(point_x, point_y, n,
length, width);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function to calculate the largest # area unguarded by towers def maxArea(point_x, point_y, n, length, width): # Sort the x-coordinates of the list point_x.sort() # Sort the y-coordinates of the list point_y.sort() # dx --> maximum uncovered # tiles in x coordinates dx = point_x[0] # dy --> maximum uncovered # tiles in y coordinates dy = point_y[0] # Calculate the maximum uncovered # distances for both x and y coordinates for i in range(1, n): dx = max(dx, point_x[i] - point_x[i - 1]) dy = max(dy, point_y[i] - point_y[i - 1]) dx = max(dx, (length + 1) - point_x[n - 1]) dy = max(dy, (width + 1) - point_y[n - 1]) # Largest unguarded area is # max(dx)-1 * max(dy)-1 print((dx - 1) * (dy - 1)) # Driver Code if __name__ == "__main__": # Length and width of the grid length = 15 width = 8 # No of guard towers n = 3 # Array to store the x and # y coordinates point_x = [ 3, 11, 8 ] point_y = [ 8, 2, 6 ] # Function call maxArea(point_x, point_y, n, length, width) # This code is contributed by akhilsaini
C#
// C# Program for the above approach
using System;
class GFG{
// Function to calculate the largest
// area unguarded by towers
static void maxArea(int[] point_x, int[] point_y,
int n, int length, int width)
{
// Sort the x-coordinates of the list
Array.Sort(point_x);
// Sort the y-coordinates of the list
Array.Sort(point_y);
// dx --> maximum uncovered
// tiles in x coordinates
int dx = point_x[0];
// dy --> maximum uncovered
// tiles in y coordinates
int dy = point_y[0];
// Calculate the maximum uncovered
// distances for both x and y coordinates
for(int i = 1; i < n; i++)
{
dx = Math.Max(dx, point_x[i] -
point_x[i - 1]);
dy = Math.Max(dy, point_y[i] -
point_y[i - 1]);
}
dx = Math.Max(dx, (length + 1) -
point_x[n - 1]);
dy = Math.Max(dy, (width + 1) -
point_y[n - 1]);
// Largest unguarded area is
// max(dx)-1 * max(dy)-1
Console.WriteLine((dx - 1) * (dy - 1));
}
// Driver Code
static public void Main()
{
// Length and width of the grid
int length = 15, width = 8;
// No of guard towers
int n = 3;
// Array to store the x and
// y coordinates
int[] point_x = { 3, 11, 8 };
int[] point_y = { 8, 2, 6 };
// Function call
maxArea(point_x, point_y, n,
length, width);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program for the
// above approach
// Function to calculate the largest
// area unguarded by towers
function maxArea(polet_x, polet_y,
n, length, width)
{
// Sort the x-coordinates of the list
polet_x.sort((a, b) => a - b);;
// Sort the y-coordinates of the list
polet_y.sort((a, b) => a - b);;
// dx --> maximum uncovered
// tiles in x coordinates
let dx = polet_x[0];
// dy --> maximum uncovered
// tiles in y coordinates
let dy = polet_y[0];
// Calculate the maximum uncovered
// distances for both x and y coordinates
for(let i = 1; i < n; i++)
{
dx = Math.max(dx, polet_x[i] -
polet_x[i - 1]);
dy = Math.max(dy, polet_y[i] -
polet_y[i - 1]);
}
dx = Math.max(dx, (length + 1) -
polet_x[n - 1]);
dy = Math.max(dy, (width + 1) -
polet_y[n - 1]);
// Largest unguarded area is
// max(dx)-1 * max(dy)-1
document.write((dx - 1) * (dy - 1));
}
// Driver Code
// Length and width of the grid
let length = 15, width = 8;
// No of guard towers
let n = 3;
// Array to store the x and
// y coordinates
let polet_x = [ 3, 11, 8 ];
let polet_y = [ 8, 2, 6 ];
// Function call
maxArea(polet_x, polet_y, n,
length, width);
</script>
Producción:
12
Complejidad de Tiempo: (N * log N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por amishbharti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA