Given a matrix of ' O ' and ' X ' , find the largest subsquare surrounded by ' X ' | A C ++ program to find the largest subsquare surrounded by ' X ' in a given matrix of ' O ' and ' 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  6 NEW_LINE int maximumSubSquare ( int arr [ ] [ N ] ) { pair < int , int > dp [ 51 ] [ 51 ] ; int maxside [ 51 ] [ 51 ] ; memset ( maxside , 0 , sizeof ( maxside ) ) ; 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 ] . first = 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 ] . second = y ; } } int maxval = 0 , val = 0 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { val = min ( dp [ i ] [ j ] . first , dp [ i ] [ j ] . second ) ; if ( dp [ i ] [ j - val + 1 ] . second >= val && dp [ i - val + 1 ] [ j ] . first >= val ) maxside [ i ] [ j ] = val ; else maxside [ i ] [ j ] = 0 ; maxval = max ( maxval , maxside [ i ] [ j ] ) ; } } return maxval ; } int main ( ) { int mat [ ] [ N ] = { { ' 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 ' } , } ; cout << maximumSubSquare ( mat ) ; return 0 ; }