Queries on number of Binary sub | Python 3 Program to answer queries on number of submatrix of given size ; Solve each query on matrix ; For each of the cell . ; finding submatrix size of oth row and column . ; intermediate cells . ; Find frequency of each distinct size for 0 s and 1 s . ; Find the Cumulative Sum . ; Output the answer for each query ; Driver Program
MAX = 100 NEW_LINE N = 5 NEW_LINE M = 4 NEW_LINE def solveQuery ( n , m , mat , q , a , binary ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( m ) ] for y in range ( n ) ] NEW_LINE max = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT elif ( ( mat [ i ] [ j ] == mat [ i - 1 ] [ j ] ) and ( mat [ i ] [ j ] == mat [ i ] [ j - 1 ] ) and ( mat [ i ] [ j ] == mat [ i - 1 ] [ j - 1 ] ) ) : NEW_LINE INDENT dp [ i ] [ j ] = ( min ( dp [ i - 1 ] [ j ] , min ( dp [ i - 1 ] [ j - 1 ] , dp [ i ] [ j - 1 ] ) ) + 1 ) NEW_LINE if ( max < dp [ i ] [ j ] ) : NEW_LINE INDENT max = dp [ i ] [ j ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT freq0 = [ 0 ] * MAX NEW_LINE freq1 = [ 0 ] * MAX NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 0 ) : NEW_LINE INDENT freq0 [ dp [ i ] [ j ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq1 [ dp [ i ] [ j ] ] += 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( max - 1 , - 1 , - 1 ) : NEW_LINE INDENT freq0 [ i ] += freq0 [ i + 1 ] NEW_LINE freq1 [ i ] += freq1 [ i + 1 ] NEW_LINE DEDENT for i in range ( q ) : NEW_LINE INDENT if ( binary [ i ] == 0 ) : NEW_LINE INDENT print ( freq0 [ a [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( freq1 [ a [ i ] ] ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE m = 4 NEW_LINE mat = [ [ 0 , 0 , 1 , 1 ] , [ 0 , 0 , 1 , 0 ] , [ 0 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 ] , [ 0 , 1 , 1 , 1 ] ] NEW_LINE q = 2 NEW_LINE a = [ 2 , 2 ] NEW_LINE binary = [ 1 , 0 ] NEW_LINE solveQuery ( n , m , mat , q , a , binary ) NEW_LINE DEDENT