Check if a matrix contains a square submatrix with 0 as boundary element | Function checks if square with all 0 's in boundary exists in the matrix ; r1 is the top row , c1 is the left col r2 is the bottom row , c2 is the right ; Function checks if the boundary of the square consists of 0 's ; Driver Code
def squareOfZeroes ( ) : NEW_LINE INDENT global matrix , cache NEW_LINE lastIdx = len ( matrix ) - 1 NEW_LINE return hasSquareOfZeroes ( 0 , 0 , lastIdx , lastIdx ) NEW_LINE DEDENT def hasSquareOfZeroes ( r1 , c1 , r2 , c2 ) : NEW_LINE INDENT global matrix , cache NEW_LINE if ( r1 >= r2 or c1 >= c2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT key = ( str ( r1 ) + ' - ' + str ( c1 ) + ' - ' + str ( r2 ) + ' - ' + str ( c2 ) ) NEW_LINE if ( key in cache ) : NEW_LINE INDENT return cache [ key ] NEW_LINE DEDENT cache [ key ] = ( isSquareOfZeroes ( r1 , c1 , r2 , c2 ) or hasSquareOfZeroes ( r1 + 1 , c1 + 1 , r2 - 1 , c2 - 1 ) ) NEW_LINE cache [ key ] = ( cache [ key ] or hasSquareOfZeroes ( r1 , c1 + 1 , r2 - 1 , c2 ) or hasSquareOfZeroes ( r1 + 1 , c1 , r2 , c2 - 1 ) ) NEW_LINE cache [ key ] = ( cache [ key ] or hasSquareOfZeroes ( r1 + 1 , c1 + 1 , r2 , c2 ) or hasSquareOfZeroes ( r1 , c1 , r2 - 1 , c2 - 1 ) ) NEW_LINE return cache [ key ] NEW_LINE DEDENT def isSquareOfZeroes ( r1 , c1 , r2 , c2 ) : NEW_LINE INDENT global matrix NEW_LINE for row in range ( r1 , r2 + 1 ) : NEW_LINE INDENT if ( matrix [ row ] [ c1 ] != 0 or matrix [ row ] [ c2 ] != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT for col in range ( c1 , c2 + 1 ) : NEW_LINE INDENT if ( matrix [ r1 ] [ col ] != 0 or matrix [ r2 ] [ col ] != 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT cache = { } NEW_LINE matrix = [ [ 1 , 1 , 1 , 0 , 1 , 0 ] , [ 0 , 0 , 0 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 1 , 0 , 1 ] , [ 0 , 1 , 1 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 0 , 1 ] ] NEW_LINE ans = squareOfZeroes ( ) NEW_LINE if ( ans == 1 ) : NEW_LINE INDENT print ( " True " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " False " ) NEW_LINE DEDENT DEDENT