Find number of square of area Z which can be built in a matrix having blocked regions | Python3 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
from math import sqrt NEW_LINE def subgrids ( N , Z , row , col , r , d ) : NEW_LINE INDENT conrow = [ ] ; NEW_LINE concol = [ ] ; NEW_LINE K = int ( sqrt ( Z ) ) ; NEW_LINE conrow . append ( row [ 0 ] - 0 - 1 ) NEW_LINE conrow . append ( N + 1 - row [ r - 1 ] - 1 ) NEW_LINE for i in range ( 1 , r ) : NEW_LINE INDENT conrow . append ( row [ i ] - row [ i - 1 ] - 1 ) ; NEW_LINE DEDENT concol . append ( col [ 0 ] - 0 - 1 ) NEW_LINE concol . append ( N + 1 - col [ d - 1 ] - 1 ) NEW_LINE for i in range ( 1 , d ) : NEW_LINE INDENT concol . append ( col [ i ] - col [ i - 1 ] - 1 ) ; NEW_LINE DEDENT row_size = len ( conrow ) NEW_LINE col_size = len ( concol ) NEW_LINE answer = 0 NEW_LINE for i in range ( row_size ) : NEW_LINE INDENT for j in range ( col_size ) : NEW_LINE INDENT total = ( concol [ j ] // K ) * ( conrow [ i ] // K ) NEW_LINE answer += ( total ) NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 8 ; Z = 4 NEW_LINE row = [ 4 , 6 ] NEW_LINE col = [ 3 , 8 ] NEW_LINE r = len ( row ) NEW_LINE d = len ( col ) NEW_LINE print ( subgrids ( N , Z , row , col , r , d ) ) NEW_LINE DEDENT