Queries to count minimum flips required to fill a binary submatrix with 0 s only | Python3 program for the above approach ; Function to compute the matrix prefixCnt [ M ] [ N ] from mat [ M ] [ N ] such that prefixCnt [ i ] [ j ] stores the count of 0 's from (0, 0) to (i, j) ; Initialize prefixCnt [ i ] [ j ] with 1 if mat [ i ] [ j ] is 0 ; Otherwise , assign with 0 ; Calculate prefix sum for each row ; Calculate prefix sum for each column ; Function to compute count of 0 's in submatrix from (pi, pj) to (qi, qj) from prefixCnt[M][N] ; Initialize that count of 0 's  in the sub-matrix within  indices (0, 0) to (qi, qj) ; Subtract count of 0 's within  indices (0, 0) and (pi-1, qj) ; Subtract count of 0 's within  indices (0, 0) and (qi, pj-1) ; Add prefixCnt [ pi - 1 ] [ pj - 1 ] because its value has been added once but subtracted twice ; Function to count the 0 s in the each given submatrix ; Stores the prefix sum of each row and column ; Compute matrix prefixCnt [ ] [ ] ; Function Call for each query ; Driver Code ; Given matrix ; Function Call
M = 6 NEW_LINE N = 7 NEW_LINE def preCompute ( mat , prefixCnt ) : NEW_LINE INDENT for i in range ( M ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 0 ) : NEW_LINE INDENT prefixCnt [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT prefixCnt [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( M ) : NEW_LINE INDENT for j in range ( 1 , N ) : NEW_LINE INDENT prefixCnt [ i ] [ j ] += prefixCnt [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , M ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT prefixCnt [ i ] [ j ] += prefixCnt [ i - 1 ] [ j ] NEW_LINE DEDENT DEDENT return prefixCnt NEW_LINE DEDENT def countQuery ( prefixCnt , pi , pj , qi , qj ) : NEW_LINE INDENT cnt = prefixCnt [ qi ] [ qj ] NEW_LINE if ( pi > 0 ) : NEW_LINE INDENT cnt -= prefixCnt [ pi - 1 ] [ qj ] NEW_LINE DEDENT if ( pj > 0 ) : NEW_LINE INDENT cnt -= prefixCnt [ qi ] [ pj - 1 ] NEW_LINE DEDENT if ( pi > 0 and pj > 0 ) : NEW_LINE INDENT cnt += prefixCnt [ pi - 1 ] [ pj - 1 ] NEW_LINE DEDENT return cnt NEW_LINE DEDENT def count0s ( mat , Q , sizeQ ) : NEW_LINE INDENT prefixCnt = [ [ 0 for i in range ( N ) ] for i in range ( M ) ] NEW_LINE prefixCnt = preCompute ( mat , prefixCnt ) NEW_LINE for i in range ( sizeQ ) : NEW_LINE INDENT print ( countQuery ( prefixCnt , Q [ i ] [ 0 ] , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , Q [ i ] [ 3 ] ) , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 0 , 1 , 0 , 1 , 1 , 1 , 0 ] , [ 1 , 0 , 1 , 1 , 1 , 0 , 1 ] , [ 1 , 1 , 0 , 0 , 1 , 1 , 0 ] , [ 1 , 1 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 1 , 0 , 1 , 1 , 1 ] , [ 1 , 1 , 0 , 1 , 1 , 0 , 1 ] ] NEW_LINE Q = [ [ 0 , 1 , 3 , 2 ] , [ 2 , 2 , 4 , 5 ] , [ 4 , 3 , 5 , 6 ] ] NEW_LINE sizeQ = len ( Q ) NEW_LINE count0s ( mat , Q , sizeQ ) NEW_LINE DEDENT