text: Largest Square in a Binary Matrix with at most K 1 s for multiple Queries | C # 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  ; Precomputing the countDP prefix sum of the matrix ; Loop to solve Queries ; Calculating the maximum possible distance of the centre from edge ; Calculating the number of 1 s in the submatrix ; Driver Code
code: using System ; class GFG { 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 ] ; 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 ] ; 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 x1 = i - k , x2 = i + k ; int y1 = j - k , y2 = j + k ; 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 + " STRNEWLINE " ) ; } } 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 ) ; } }