Largest Square

Posted: 28 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a binary grid containing only 0s and 1s. You are also given an integer, ‘K’ and you are asked ‘Q’ queries. In each query, you are given the location of a cell. For each query, you need to find the largest square containing at most ‘K’ 1s and having its center as the cell given in the query.

Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, where ‘N’ and ‘M’ denote the dimensions of the binary grid. Then ‘N’ lines follow.

Each of these ‘N’ lines contains ‘M’ space-separated integers denoting the elements of the ‘i-th’ row. Each of these integers is either a 0 or a 1.

The next line contains two space-separated integers, ‘K’ and ‘Q’, where ‘K’ denotes the maximum number of 1s that a square can have and ‘Q’ denotes the number of queries to be run. Now, ‘Q’ lines follow.

Each of these ‘Q’ lines contains two space-separated integers, ‘A’ and ‘B’, denoting that in this query, the required square must have the cell located at ‘A-th’ row and ‘B-th’ column as its center.
Output Format:
For each test case, print ‘Q’ space-separated integers, denoting the length of the largest required square in each query.

Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N,M <= 500
1 <= Q <= 1000
1 <= K <= N*M

Where ‘T’ denotes the number of test cases and ‘N’ and ‘M’ denote the dimensions of the binary grid. ‘Q’ denotes the number of queries and ‘K’ is the maximum number of 1s that the required square can have.

Time Limit: 1 sec.
Approach 1

The approach is to simply try to solve each query independently. We will start at the given cell and count the number of 1s in it and one by one count the number of 1s in each square whose center is that cell. As soon as this count becomes greater than ‘K’ we stop and return the length of the previous square because the required square is allowed to have not more than ‘K’ 1s.

 

 

Steps:

 

  1. Define a vector, say results, to store the result of each query. We will return this after solving the result of each query.
  2. Store the value of grid.size() in a variable, say N.
  3. Store the value of grid[0].size() in a variable, say M. 
  4. Run a loop from i=0 to i<queries.size, and do:
    1. Declare a variable, say cntrY, and make it equal to queries[i][0]. Declare another variable, say cntrX, and make it equal to queries[i][1]. These two values are the location of the cell which should serve as the center of the possible squares.
    2. Declare a variable, say nearestEdgeDist, to store the value of the distance of the nearest edge of the grid from the center cell. Formally, make nearestEdgeDist = min(cntrY, n - cntrY, cntrX, m - cntrX).
    3. Define a variable, say sideLength, to store the length of the biggest square meeting all the required conditions.
    4. Run a loop from len=0 to len<=nearestEdgeDist, and do:
      1. Initialize a variable, say oneCount, to store the count of 1s in the present square.
      2. Run a loop from row=cntrY-len to row<=cntrY+len and another loop from col=cntrX-len to col<=cntrX+len, and do:
        1. If grid[row][col] has a value 1, then increase the count of oneCount.
      3. If the value of oneCount is greater than K, then we break out of the loop because this square contains more 1s than K, and naturally, any square bigger than this square will contain more 1s than K.
      4. If the count of 1s is not more than K, then that means that square is the largest possible square so far and we make sideLength = 2 * len  +1.
    5. Once, we have considered all possible squares, we have our answer for this query in the variable, sideLength, and we can push it in the vector, results.
  5. After solving the results for each query, we can return the vector, results.
Try Problem