Dada una array A[][] que consta de coordenadas de N rectángulos tales que {A[i][0], A[i][1]} representa la coordenada inferior izquierda del rectángulo y {A[i][2], A [i][3]} que representa la coordenada superior derecha del rectángulo, la tarea es encontrar el número total de celdas cubiertas por todos los rectángulos.
Ejemplos:
Entrada: N = 2,
A[][] = {{1, 1, 3, 3}, {2, 1, 4, 2}}
Salida: 5
Explicación:
El primer rectángulo cubre las siguientes 4 celdas:
{(1, 1), (1, 2), (2, 2), (2, 1)}, {(1, 2), (1, 3), (2, 3), (2, 2)}, {(2, 1), (2, 2), (3, 2), (3, 1)}, {(2, 2), (2, 3), ( 3, 3), (3, 2)}
El segundo rectángulo encierra 2 celdas:
{(2, 1), (2, 2), (3, 2), (3, 1)}, {(3, 1), (3, 2), (4, 2), (4, 1)}
Por lo tanto, ambos rectángulos cubren 5 celdas (ya que 1 celda se superpone)Entrada: N = 3,
A[][] = {{1, 3, 4, 5}, {3, 1, 7, 4}, {5, 3, 8, 6}}
Salida: 24
Enfoque:
siga los pasos a continuación para resolver el problema:
- Cree una array booleana arr[MAX][MAX] , donde arr[i][j] = 1 si(i, j) está encerrado por cualquiera de los rectángulos dados. De lo contrario, arr[i][j] = 0.
- Para cada rectángulo, itere desde abajo a la izquierda hasta arriba a la derecha y para todos los cuadros (i, j) márquelos arr[i][j] = 1.
- Finalmente, mantendremos un área variable para almacenar el número de celdas encerradas. Incrementa el área si arr[i][j] == 1 .
- Imprime el valor final del área .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// number of cells enclosed
// by the given rectangles
#include <bits/stdc++.h>
using namespace std;
#define MAX 1001
bool arr[MAX][MAX];
// Update the coordinates lying
// within the rectangle
void updateArray(int x1, int y1,
int x2, int y2)
{
for (int i = x1; i < x2; i++) {
for (int j = y1; j < y2; j++) {
// Update arr[i][j] for
// all (i, j) lying within
// the rectangle
arr[i][j] = true;
}
}
}
// Function to return the total
// area covered by rectangles
int findAreaCovered()
{
// Stores the number
// of cells
int area = 0;
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
// arr[i]][[j]==1 means that grid
// is filled by some rectangle
if (arr[i][j] == true) {
area++;
}
}
}
return area;
}
// Driver Code
int main()
{
int N = 3;
// (A[i][0], A[i][1]) denotes the
// coordinate of the bottom
// left of the rectangle
// (A[i][2], A[i][3]) denotes the
// coordinate of upper right
// of the rectangle
vector<vector<int> > A = {
{ 1, 3, 4, 5 },
{ 3, 1, 7, 4 },
{ 5, 3, 8, 6 }
};
// Update the coordinates that
// lie within the rectangle
for (int i = 0; i < N; i++) {
updateArray(A[i][0], A[i][1],
A[i][2], A[i][3]);
}
int area = findAreaCovered();
cout << area;
return 0;
}
Java
// Java program to find the number
// of cells enclosed by the given
// rectangles
class GFG{
static final int MAX = 1001;
static boolean [][]arr = new boolean[MAX][MAX];
// Update the coordinates lying
// within the rectangle
static void updateArray(int x1, int y1,
int x2, int y2)
{
for(int i = x1; i < x2; i++)
{
for(int j = y1; j < y2; j++)
{
// Update arr[i][j] for
// all (i, j) lying within
// the rectangle
arr[i][j] = true;
}
}
}
// Function to return the total
// area covered by rectangles
static int findAreaCovered()
{
// Stores the number
// of cells
int area = 0;
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
// arr[i]][[j]==1 means that grid
// is filled by some rectangle
if (arr[i][j] == true)
{
area++;
}
}
}
return area;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
// (A[i][0], A[i][1]) denotes the
// coordinate of the bottom
// left of the rectangle
// (A[i][2], A[i][3]) denotes the
// coordinate of upper right
// of the rectangle
int [][]A = { { 1, 3, 4, 5 },
{ 3, 1, 7, 4 },
{ 5, 3, 8, 6 } };
// Update the coordinates that
// lie within the rectangle
for(int i = 0; i < N; i++)
{
updateArray(A[i][0], A[i][1],
A[i][2], A[i][3]);
}
int area = findAreaCovered();
System.out.print(area);
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 program to find the # number of cells enclosed # by the given rectangles MAX = 1001 arr = [[False for i in range(MAX)] for j in range(MAX)] # Update the coordinates lying # within the rectangle def updateArray(x1, y1, x2, y2): for i in range(x1, x2): for j in range(y1, y2): # Update arr[i][j] for # all (i, j) lying within # the rectangle arr[i][j] = True # Function to return the total # area covered by rectangles def findAreaCovered(): # Stores the number # of cells area = 0 for i in range(MAX): for j in range(MAX): # arr[i]][[j]==1 means that grid # is filled by some rectangle if arr[i][j]: area += 1 return area # Driver code if __name__=="__main__": N = 3 # (A[i][0], A[i][1]) denotes the # coordinate of the bottom # left of the rectangle # (A[i][2], A[i][3]) denotes the # coordinate of upper right # of the rectangle A = [ [ 1, 3, 4, 5 ], [ 3, 1, 7, 4 ], [ 5, 3, 8, 6 ] ]; # Update the coordinates that # lie within the rectangle for i in range(N): updateArray(A[i][0], A[i][1], A[i][2], A[i][3]); area = findAreaCovered(); print(area) # This code is contributed by rutvik_56
C#
// C# program to find the number
// of cells enclosed by the given
// rectangles
using System;
class GFG{
static readonly int MAX = 1001;
static bool [,]arr = new bool[MAX, MAX];
// Update the coordinates lying
// within the rectangle
static void updateArray(int x1, int y1,
int x2, int y2)
{
for(int i = x1; i < x2; i++)
{
for(int j = y1; j < y2; j++)
{
// Update arr[i,j] for
// all (i, j) lying within
// the rectangle
arr[i, j] = true;
}
}
}
// Function to return the total
// area covered by rectangles
static int findAreaCovered()
{
// Stores the number
// of cells
int area = 0;
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
// arr[i],[j]==1 means that grid
// is filled by some rectangle
if (arr[i, j] == true)
{
area++;
}
}
}
return area;
}
// Driver Code
public static void Main(String[] args)
{
int N = 3;
// (A[i,0], A[i,1]) denotes the
// coordinate of the bottom
// left of the rectangle
// (A[i,2], A[i,3]) denotes the
// coordinate of upper right
// of the rectangle
int [,]A = { { 1, 3, 4, 5 },
{ 3, 1, 7, 4 },
{ 5, 3, 8, 6 } };
// Update the coordinates that
// lie within the rectangle
for(int i = 0; i < N; i++)
{
updateArray(A[i, 0], A[i, 1],
A[i, 2], A[i, 3]);
}
int area = findAreaCovered();
Console.Write(area);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the above approach
let MAX = 1001;
let arr = new Array(MAX);
for (var i = 0; i < arr.length; i++) {
arr[i] = new Array(2);
}
// Update the coordinates lying
// within the rectangle
function updateArray(x1, y1, x2, y2)
{
for(let i = x1; i < x2; i++)
{
for(let j = y1; j < y2; j++)
{
// Update arr[i][j] for
// all (i, j) lying within
// the rectangle
arr[i][j] = true;
}
}
}
// Function to return the total
// area covered by rectangles
function findAreaCovered()
{
// Stores the number
// of cells
let area = 0;
for(let i = 0; i < MAX; i++)
{
for(let j = 0; j < MAX; j++)
{
// arr[i]][[j]==1 means that grid
// is filled by some rectangle
if (arr[i][j] == true)
{
area++;
}
}
}
return area;
}
// Driver Code
let N = 3;
// (A[i][0], A[i][1]) denotes the
// coordinate of the bottom
// left of the rectangle
// (A[i][2], A[i][3]) denotes the
// coordinate of upper right
// of the rectangle
let A = [[ 1, 3, 4, 5 ],
[ 3, 1, 7, 4 ],
[ 5, 3, 8, 6 ]];
// Update the coordinates that
// lie within the rectangle
for(let i = 0; i < N; i++)
{
updateArray(A[i][0], A[i][1],
A[i][2], A[i][3]);
}
let area = findAreaCovered();
document.write(area);
</script>
Producción:
24
Tiempo Complejidad : O (N 3 )
Espacio Auxiliar : O (N 2 )