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
N = 6 NEW_LINE def maximumSubSquare ( arr ) : NEW_LINE INDENT dp = [ [ [ - 1 , - 1 ] for i in range ( 51 ) ] for j in range ( 51 ) ] NEW_LINE maxside = [ [ 0 for i in range ( 51 ) ] for j in range ( 51 ) ] NEW_LINE x = 0 NEW_LINE y = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT x = 0 NEW_LINE for j in range ( N ) : NEW_LINE INDENT if ( arr [ i ] [ j ] == ' X ' ) : NEW_LINE INDENT x += 1 NEW_LINE DEDENT else : NEW_LINE INDENT x = 0 NEW_LINE DEDENT dp [ i ] [ j ] [ 0 ] = x NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT if ( arr [ j ] [ i ] == ' X ' ) : NEW_LINE INDENT y += 1 NEW_LINE DEDENT else : NEW_LINE INDENT y = 0 NEW_LINE DEDENT dp [ j ] [ i ] [ 1 ] = y NEW_LINE DEDENT DEDENT maxval = 0 NEW_LINE val = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT val = min ( dp [ i ] [ j ] [ 0 ] , dp [ i ] [ j ] [ 1 ] ) NEW_LINE if ( dp [ i ] [ j - val + 1 ] [ 1 ] >= val and dp [ i - val + 1 ] [ j ] [ 0 ] >= val ) : NEW_LINE INDENT maxside [ i ] [ j ] = val NEW_LINE DEDENT else : NEW_LINE INDENT maxside [ i ] [ j ] = 0 NEW_LINE DEDENT maxval = max ( maxval , maxside [ i ] [ j ] ) NEW_LINE DEDENT DEDENT return maxval NEW_LINE DEDENT 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 ' ] ] NEW_LINE print ( maximumSubSquare ( mat ) ) NEW_LINE