Count all square sub | Python3 program to count total number of k x k sub matrix whose sum is greater than the given number S ; Function to create prefix sum matrix from the given matrix ; Store first value in table ; Initialize first row of matrix ; Initialize first column of matrix ; Initialize rest table with sum ; Utility function to count the submatrix whose sum is greater than the S ; Loop to iterate over all the possible positions of the given matrix mat [ ] [ ] ; Condition to check , if K x K is first sub matrix ; Condition to check sub - matrix has no margin at top ; Condition when sub matrix has no margin at left ; Condition when submatrix has margin at top and left ; Increment count , If sub matrix sum is greater than S ; Function to count submatrix of size k x k such that sum if greater than or equal to S ; For loop to initialize prefix sum matrix with zero , initially ; Function to create the prefix sum matrix ; Driver Code ; Print total number of sub matrix
dim = 5 NEW_LINE def createTable ( mtrx , k , p , dp ) : NEW_LINE INDENT dp [ 0 ] [ 0 ] = mtrx [ 0 ] [ 0 ] NEW_LINE for j in range ( 1 , dim ) : NEW_LINE INDENT dp [ 0 ] [ j ] = mtrx [ 0 ] [ j ] + dp [ 0 ] [ j - 1 ] NEW_LINE DEDENT for i in range ( 1 , dim ) : NEW_LINE INDENT dp [ i ] [ 0 ] = mtrx [ i ] [ 0 ] + dp [ i - 1 ] [ 0 ] NEW_LINE DEDENT for i in range ( 1 , dim ) : NEW_LINE INDENT for j in range ( 1 , dim ) : NEW_LINE INDENT dp [ i ] [ j ] = ( mtrx [ i ] [ j ] + dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] - dp [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT def countSubMatrixUtil ( dp , k , p ) : NEW_LINE INDENT count = 0 NEW_LINE subMatSum = 0 NEW_LINE for i in range ( k - 1 , dim ) : NEW_LINE INDENT for j in range ( k - 1 , dim , 1 ) : NEW_LINE INDENT if ( i == ( k - 1 ) or j == ( k - 1 ) ) : NEW_LINE INDENT if ( i == ( k - 1 ) and j == ( k - 1 ) ) : NEW_LINE INDENT subMatSum = dp [ i ] [ j ] NEW_LINE DEDENT elif ( i == ( k - 1 ) ) : NEW_LINE INDENT subMatSum = dp [ i ] [ j ] - dp [ i ] [ j - k ] NEW_LINE DEDENT else : NEW_LINE INDENT subMatSum = dp [ i ] [ j ] - dp [ i - k ] [ j ] NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT subMatSum = ( dp [ i ] [ j ] - dp [ i - k ] [ j ] - dp [ i ] [ j - k ] + dp [ i - k ] [ j - k ] ) NEW_LINE DEDENT if ( subMatSum >= p ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT def countSubMatrix ( mtrx , k , p ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( dim ) ] for j in range ( dim ) ] NEW_LINE for i in range ( dim ) : NEW_LINE INDENT for j in range ( dim ) : NEW_LINE INDENT dp [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT createTable ( mtrx , k , p , dp ) NEW_LINE return countSubMatrixUtil ( dp , k , p ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mtrx = [ [ 1 , 7 , 1 , 1 , 1 ] , [ 2 , 2 , 2 , 2 , 2 ] , [ 3 , 9 , 6 , 7 , 3 ] , [ 4 , 3 , 2 , 4 , 5 ] , [ 5 , 1 , 5 , 3 , 1 ] ] NEW_LINE k = 3 NEW_LINE p = 35 NEW_LINE print ( countSubMatrix ( mtrx , k , p ) ) NEW_LINE DEDENT