Find size of the largest ' + ' formed by all ones in a binary matrix | size of binary square matrix ; Function to find the size of the largest ' + ' formed by all 1 's in given binary matrix ; left [ j ] [ j ] , right [ i ] [ j ] , top [ i ] [ j ] and bottom [ i ] [ j ] store maximum number of consecutive 1 's present to the left,  right, top and bottom of mat[i][j] including  cell(i, j) respectively ; initialize above four matrix ; initialize first row of top ; initialize last row of bottom ; initialize first column of left ; initialize last column of right ; fill all cells of above four matrix ; calculate left matrix ( filled left to right ) ; calculate top matrix ; calculate new value of j to calculate value of bottom ( i , j ) and right ( i , j ) ; calculate bottom matrix ; calculate right matrix ; revert back to old j ; n stores length of longest ' + ' found so far ; compute longest + ; find minimum of left ( i , j ) , right ( i , j ) , top ( i , j ) , bottom ( i , j ) ; largest + would be formed by a cell that has maximum value ; 4 directions of length n - 1 and 1 for middle cell ; matrix contains all 0 's ; Driver Code
N = 10 NEW_LINE def findLargestPlus ( mat ) : NEW_LINE INDENT left = [ [ 0 for x in range ( N ) ] for y in range ( N ) ] NEW_LINE right = [ [ 0 for x in range ( N ) ] for y in range ( N ) ] NEW_LINE top = [ [ 0 for x in range ( N ) ] for y in range ( N ) ] NEW_LINE bottom = [ [ 0 for x in range ( N ) ] for y in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT top [ 0 ] [ i ] = mat [ 0 ] [ i ] NEW_LINE bottom [ N - 1 ] [ i ] = mat [ N - 1 ] [ i ] NEW_LINE left [ i ] [ 0 ] = mat [ i ] [ 0 ] NEW_LINE right [ i ] [ N - 1 ] = mat [ i ] [ N - 1 ] NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( 1 , N ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT left [ i ] [ j ] = left [ i ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT left [ i ] [ j ] = 0 NEW_LINE DEDENT if ( mat [ j ] [ i ] == 1 ) : NEW_LINE INDENT top [ j ] [ i ] = top [ j - 1 ] [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT top [ j ] [ i ] = 0 NEW_LINE DEDENT j = N - 1 - j NEW_LINE if ( mat [ j ] [ i ] == 1 ) : NEW_LINE INDENT bottom [ j ] [ i ] = bottom [ j + 1 ] [ i ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT bottom [ j ] [ i ] = 0 NEW_LINE DEDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT right [ i ] [ j ] = right [ i ] [ j + 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right [ i ] [ j ] = 0 NEW_LINE DEDENT j = N - 1 - j NEW_LINE DEDENT DEDENT n = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT l = min ( min ( top [ i ] [ j ] , bottom [ i ] [ j ] ) , min ( left [ i ] [ j ] , right [ i ] [ j ] ) ) NEW_LINE if ( l > n ) : NEW_LINE INDENT n = l NEW_LINE DEDENT DEDENT DEDENT if ( n ) : NEW_LINE INDENT return 4 * ( n - 1 ) + 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT mat = [ [ 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 ] , [ 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 ] , [ 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 ] , [ 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 ] , [ 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 ] , [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 ] , [ 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 ] , [ 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 ] , [ 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 ] ] NEW_LINE print ( findLargestPlus ( mat ) ) NEW_LINE DEDENT