Find number of square of area Z which can be built in a matrix having blocked regions | C ++ implementation of the approach ; Function to calculate the number of square areas of size K * K ; Row array and column array to store the lengths of differences between consecutive rows / columns ; Fill the conrow vector ; Fill the concol vector ; To store the required answer ; Every pair of row size and column size would result in an unblocked region ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int subgrids ( int N , int Z , int row [ ] , int col [ ] , int r , int c ) { vector < int > conrow ; vector < int > concol ; int K = sqrt ( Z ) ; conrow . push_back ( row [ 0 ] - 0 - 1 ) ; conrow . push_back ( N + 1 - row [ r - 1 ] - 1 ) ; for ( int i = 1 ; i < r ; i ++ ) { conrow . push_back ( row [ i ] - row [ i - 1 ] - 1 ) ; } concol . push_back ( col [ 0 ] - 0 - 1 ) ; concol . push_back ( N + 1 - col - 1 ) ; for ( int i = 1 ; i < c ; i ++ ) { concol . push_back ( col [ i ] - col [ i - 1 ] - 1 ) ; } int row_size = conrow . size ( ) ; int col_size = concol . size ( ) ; int answer = 0 ; for ( int i = 0 ; i < row_size ; i ++ ) { for ( int j = 0 ; j < col_size ; j ++ ) { int total = ( concol [ j ] / K ) * ( conrow [ i ] / K ) ; answer += ( total ) ; } } return answer ; } int main ( ) { int N = 8 , Z = 4 ; int row [ ] = { 4 , 6 } ; int col [ ] = { 3 , 8 } ; int r = sizeof ( row ) / sizeof ( row [ 0 ] ) ; int c = sizeof ( col ) / sizeof ( col [ 0 ] ) ; cout << subgrids ( N , Z , row , col , r , c ) ; return 0 ; }