Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X' - GeeksforGeeks
Given a matrix where every element is either 'O' or 'X', find the largest subsquare surrounded by 'X'.
O(N3) time with extra space.
The idea is to create two auxiliary arrays hor[N][N] and ver[N][N]. The value stored in hor[i][j] is the number of horizontal continuous ‘X’ characters till mat[i][j] in mat[][]. Similarly, the value stored in ver[i][j] is the number of vertical continuous ‘X’ characters till mat[i][j] in mat[][].
For every visited entry mat[i][j], we compare the values of hor[i][j] and ver[i][j], and pick the smaller of two as we need a square. Let the smaller of two be ‘small’. After picking smaller of two, we check if both ver[][] and hor[][] for left and up edges respectively. If they have entries for the same, then we found a subsquare. Otherwise we try for small-1.
Brute Force
consider every square submatrix and check whether is has all corner edges filled with ‘X’. The time complexity of this solution is O(N4).
Related: http://massivealgorithms.blogspot.com/2015/10/given-matrix-of-o-and-x-replace-o-with.html
Read full article from Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X' - GeeksforGeeks
Given a matrix where every element is either 'O' or 'X', find the largest subsquare surrounded by 'X'.
O(N3) time with extra space.
The idea is to create two auxiliary arrays hor[N][N] and ver[N][N]. The value stored in hor[i][j] is the number of horizontal continuous ‘X’ characters till mat[i][j] in mat[][]. Similarly, the value stored in ver[i][j] is the number of vertical continuous ‘X’ characters till mat[i][j] in mat[][].
For every visited entry mat[i][j], we compare the values of hor[i][j] and ver[i][j], and pick the smaller of two as we need a square. Let the smaller of two be ‘small’. After picking smaller of two, we check if both ver[][] and hor[][] for left and up edges respectively. If they have entries for the same, then we found a subsquare. Otherwise we try for small-1.
int findSubSquare(int mat[][N]){ int max = 1; // Initialize result // Initialize the left-top value in hor[][] and ver[][] int hor[N][N], ver[N][N]; hor[0][0] = ver[0][0] = (mat[0][0] == 'X'); // Fill values in hor[][] and ver[][] for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (mat[i][j] == 'O') ver[i][j] = hor[i][j] = 0; else { hor[i][j] = (j==0)? 1: hor[i][j-1] + 1; ver[i][j] = (i==0)? 1: ver[i-1][j] + 1; } } } // Start from the rightmost-bottommost corner element and find // the largest ssubsquare with the help of hor[][] and ver[][] for (int i = N-1; i>=1; i--) { for (int j = N-1; j>=1; j--) { // Find smaller of values in hor[][] and ver[][] // A Square can only be made by taking smaller // value int small = getMin(hor[i][j], ver[i][j]); // At this point, we are sure that there is a right // vertical line and bottom horizontal line of length // at least 'small'. // We found a bigger square if following conditions // are met: // 1)If side of square is greater than max. // 2)There is a left vertical line of length >= 'small' // 3)There is a top horizontal line of length >= 'small' while (small > max) { if (ver[i][j-small+1] >= small && hor[i-small+1][j] >= small) { max = small; } small--; } } } return max;}consider every square submatrix and check whether is has all corner edges filled with ‘X’. The time complexity of this solution is O(N4).
Related: http://massivealgorithms.blogspot.com/2015/10/given-matrix-of-o-and-x-replace-o-with.html
Read full article from Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X' - GeeksforGeeks
