Given a matrix of ' O ' and ' X ' , find the largest subsquare surrounded by ' X ' | Size of given matrix is N X N ; Initialize maxside with 0 ; Fill the dp matrix horizontally . for contiguous ' X ' increment the value of x , otherwise make it 0 ; Fill the dp matrix vertically . For contiguous ' X ' increment the value of y , otherwise make it 0 ; Now check , for every value of ( i , j ) if sub - square is possible , traverse back horizontally by value val , and check if vertical contiguous ' X ' enfing at ( i , j - val + 1 ) is greater than equal to val . Similarly , check if traversing back vertically , the horizontal contiguous ' X ' ending at ( i - val + 1 , j ) is greater than equal to val . ; store the final answer in maxval ; return the final answe . ; Driver code ; Function call
class GFG { static int N = 6 ; static int maximumSubSquare ( int [ ] [ ] arr ) { int [ ] [ ] [ ] dp = new int [ 51 ] [ 51 ] [ 2 ] ; int [ ] [ ] maxside = new int [ 51 ] [ 51 ] ; for ( int [ ] row : maxside ) Arrays . fill ( row , 10 ) ; int x = 0 , y = 0 ; for ( int i = 0 ; i < N ; i ++ ) { x = 0 ; for ( int j = 0 ; j < N ; j ++ ) { if ( arr [ i ] [ j ] == ' X ' ) x += 1 ; else x = 0 ; dp [ i ] [ j ] [ 0 ] = x ; } } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( arr [ j ] [ i ] == ' X ' ) y += 1 ; else y = 0 ; dp [ j ] [ i ] [ 1 ] = y ; } } int maxval = 0 , val = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { val = Math . min ( dp [ i ] [ j ] [ 0 ] , dp [ i ] [ j ] [ 1 ] ) ; if ( dp [ i ] [ j - val + 1 ] [ 1 ] >= val && dp [ i - val + 1 ] [ j ] [ 0 ] >= val ) maxside [ i ] [ j ] = val ; else maxside [ i ] [ j ] = 0 ; maxval = Math . max ( maxval , maxside [ i ] [ j ] ) ; } } return maxval ; } public static void main ( String [ ] args ) { int mat [ ] [ ] = { { ' X ' , ' O ' , ' X ' , ' X ' , ' X ' , ' X ' } , { ' X ' , ' O ' , ' X ' , ' X ' , ' O ' , ' X ' } , { ' X ' , ' X ' , ' X ' , ' O ' , ' O ' , ' X ' } , { ' O ' , ' X ' , ' X ' , ' X ' , ' X ' , ' X ' } , { ' X ' , ' X ' , ' X ' , ' O ' , ' X ' , ' O ' } , { ' O ' , ' O ' , ' X ' , ' O ' , ' O ' , ' O ' } , } ; System . out . println ( maximumSubSquare ( mat ) ) ; } }