Given a matrix A[][] consisting of coordinates of N rectangles such that {A[i][0], A[i][1]} representing bottom left coordinate of rectangle and {A[i][2], A[i][3]} representing top right coordinate of rectangle, the task is to find the total number of cells covered by all rectangles.
Examples:
Input: N = 2,
A[][] = {{1, 1, 3, 3}, {2, 1, 4, 2}}
Output: 5
Explanation:
First rectangle covers the following 4 cells:
{(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)}
Second rectangle encloses 2 cells:
{(2, 1), (2, 2), (3, 2), (3, 1)}, {(3, 1), (3, 2), (4, 2), (4, 1)}
Hence, both the rectangles cover 5 cells (since, 1 cell overlaps)Input: N = 3,
A[][] = {{1, 3, 4, 5}, {3, 1, 7, 4}, {5, 3, 8, 6}}
Output: 24
Approach:
Follow the steps below to solve the problem:
- Create a Boolean matrix arr[MAX][MAX], where arr[i][j] = 1 if(i, j) is enclosed by any of the given rectangles. Otherwise, arr[i][j] = 0.
- For every rectangle, iterate from bottom left to top right and for all (i, j) boxes mark them arr[i][j] = 1.
- Finally, we will maintain a variable area to store the number of cells enclosed. Increment area if arr[i][j] == 1.
- Print the final value of area.
Below is the implementation of the above approach :
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 // rectanglesclass GFG{ static final int MAX = 1001;static boolean [][]arr = new boolean[MAX][MAX];// Update the coordinates lying// within the rectanglestatic 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 rectanglesstatic 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 Codepublic 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 = 1001arr = [[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 codeif __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 // rectanglesusing System;class GFG{ static readonly int MAX = 1001;static bool [,]arr = new bool[MAX, MAX];// Update the coordinates lying// within the rectanglestatic 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 rectanglesstatic 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 Codepublic 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 approachlet 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 rectanglefunction 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 rectanglesfunction 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> |
Output:
24
Time Complexity : O (N 3)
Auxiliary Space : O (N 2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
