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
< ? php $ N = 10 ; function findLargestPlus ( $ mat ) { global $ N ; $ left [ $ N ] [ $ N ] = array ( ) ; $ right [ $ N ] [ $ N ] = array ( ) ; $ top [ $ N ] [ $ N ] = array ( ) ; $ bottom [ $ N ] [ $ N ] = array ( ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { $ top [ 0 ] [ $ i ] = $ mat [ 0 ] [ $ i ] ; $ bottom [ $ N - 1 ] [ $ i ] = $ mat [ $ N - 1 ] [ $ i ] ; $ left [ $ i ] [ 0 ] = $ mat [ $ i ] [ 0 ] ; $ right [ $ i ] [ $ N - 1 ] = $ mat [ $ i ] [ $ N - 1 ] ; } for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 1 ; $ j < $ N ; $ j ++ ) { if ( $ mat [ $ i ] [ $ j ] == 1 ) $ left [ $ i ] [ $ j ] = $ left [ $ i ] [ $ j - 1 ] + 1 ; else $ left [ $ i ] [ $ j ] = 0 ; if ( $ mat [ $ j ] [ $ i ] == 1 ) $ top [ $ j ] [ $ i ] = $ top [ $ j - 1 ] [ $ i ] + 1 ; else $ top [ $ j ] [ $ i ] = 0 ; $ j = $ N - 1 - $ j ; if ( $ mat [ $ j ] [ $ i ] == 1 ) $ bottom [ $ j ] [ $ i ] = $ bottom [ $ j + 1 ] [ $ i ] + 1 ; else $ bottom [ $ j ] [ $ i ] = 0 ; if ( $ mat [ $ i ] [ $ j ] == 1 ) $ right [ $ i ] [ $ j ] = $ right [ $ i ] [ $ j + 1 ] + 1 ; else $ right [ $ i ] [ $ j ] = 0 ; $ j = $ N - 1 - $ j ; } } $ n = 0 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { for ( $ j = 0 ; $ j < $ N ; $ j ++ ) { $ len = min ( min ( $ top [ $ i ] [ $ j ] , $ bottom [ $ i ] [ $ j ] ) , min ( $ left [ $ i ] [ $ j ] , $ right [ $ i ] [ $ j ] ) ) ; if ( $ len > $ n ) $ n = $ len ; } } if ( $ n ) return 4 * ( $ n - 1 ) + 1 ; return 0 ; } $ mat = array ( array ( 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 ) , array ( 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 ) , array ( 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 ) , array ( 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 ) , array ( 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 ) , array ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 ) , array ( 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 ) , array ( 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 ) , array ( 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 ) , array ( 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 ) ) ; echo findLargestPlus ( $ mat ) ; ? >