Find all rectangles filled with 0 | Python program to find all rectangles filled with 0 ; flag to check column edge case , initializing with 0 ; flag to check row edge case , initializing with 0 ; loop breaks where first 1 encounters ; set the flag ; pass because already processed ; loop breaks where first 1 encounters ; set the flag ; fill rectangle elements with any number so that we can exclude next time ; when end point touch the boundary ; when end point touch the boundary ; retrieving the column size of array ; output array where we are going to store our output ; It will be used for storing start and end location in the same index ; storing initial position of rectangle ; will be used for the last position ; driver code
def findend ( i , j , a , output , index ) : NEW_LINE INDENT x = len ( a ) NEW_LINE y = len ( a [ 0 ] ) NEW_LINE flagc = 0 NEW_LINE flagr = 0 NEW_LINE for m in range ( i , x ) : NEW_LINE INDENT if a [ m ] [ j ] == 1 : NEW_LINE INDENT flagr = 1 NEW_LINE break NEW_LINE DEDENT if a [ m ] [ j ] == 5 : NEW_LINE INDENT pass NEW_LINE DEDENT for n in range ( j , y ) : NEW_LINE INDENT if a [ m ] [ n ] == 1 : NEW_LINE INDENT flagc = 1 NEW_LINE break NEW_LINE DEDENT a [ m ] [ n ] = 5 NEW_LINE DEDENT DEDENT if flagr == 1 : NEW_LINE INDENT output [ index ] . append ( m - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT output [ index ] . append ( m ) NEW_LINE DEDENT if flagc == 1 : NEW_LINE INDENT output [ index ] . append ( n - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT output [ index ] . append ( n ) NEW_LINE DEDENT DEDENT def get_rectangle_coordinates ( a ) : NEW_LINE INDENT size_of_array = len ( a ) NEW_LINE output = [ ] NEW_LINE index = - 1 NEW_LINE for i in range ( 0 , size_of_array ) : NEW_LINE INDENT for j in range ( 0 , len ( a [ 0 ] ) ) : NEW_LINE INDENT if a [ i ] [ j ] == 0 : NEW_LINE INDENT output . append ( [ i , j ] ) NEW_LINE index = index + 1 NEW_LINE findend ( i , j , a , output , index ) NEW_LINE DEDENT DEDENT DEDENT print ( output ) NEW_LINE DEDENT tests = [ [ 1 , 1 , 1 , 1 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 0 , 0 , 0 , 1 ] , [ 1 , 0 , 1 , 0 , 0 , 0 , 1 ] , [ 1 , 0 , 1 , 1 , 1 , 1 , 1 ] , [ 1 , 0 , 1 , 0 , 0 , 0 , 0 ] , [ 1 , 1 , 1 , 0 , 0 , 0 , 1 ] , [ 1 , 1 , 1 , 1 , 1 , 1 , 1 ] ] NEW_LINE get_rectangle_coordinates ( tests ) NEW_LINE