给定一个矩阵，其中每个元素都是’O’或’X’，找出被’X’包围的最大子正方形。 在下面的文章中，假设给定的矩阵也是一个方阵。下面给出的代码可以很容易地扩展到矩形矩阵。
null
例如：
Input: mat[N][N] = { {'X', 'O', 'X', 'X', 'X'}, {'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'O', 'X', 'O'}, {'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'O'}, };Output: 3The square submatrix starting at (1, 1) is the largestsubmatrix surrounded by 'X'Input: mat[M][N] = { {'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'O', 'X'}, {'X', 'X', 'X', 'O', 'O', 'X'}, {'X', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, };Output: 4The square submatrix starting at (0, 2) is the largestsubmatrix surrounded by 'X'
A. 简单解决方案 是要考虑每个方子矩阵，检查是否有所有的角边填充“x”。该解的时间复杂度为O（N） 4. ). 我们可以解决这个问题 在O（N）中 3. )时间 使用额外的空间。其想法是创建两个辅助数组hor[N][N]和ver[N][N]。存储在hor[i][j]中的值是在mat[]中mat[i][j]之前的水平连续“X”字符数。同样，存储在ver[i][j]中的值是在mat[]中mat[i][j]之前垂直连续的“X”字符数。
例子：
mat[6][6] = 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 Ohor[6][6] = 1 0 1 2 3 4 1 0 1 2 0 1 1 2 3 0 0 1 0 1 2 3 4 5 1 2 3 0 1 0 0 0 1 0 0 0ver[6][6] = 1 0 1 1 1 1 2 0 2 2 0 2 3 1 3 0 0 3 0 2 4 1 1 4 1 3 5 0 2 0 0 0 6 0 0 0
一旦我们在hor[]]和ver[]]中填充了值，我们就从矩阵最右下角开始，以逐行的方式向最左上角移动。对于每个访问的入口垫[i][j]，我们比较hor[i][j]和ver[i][j]的值，并选择两者中较小的一个，因为我们需要一个正方形。让两个中较小的一个“小”。在选取两个中较小的一个后，我们分别检查左边缘和上边缘的ver[]]和hor[]]是否都存在。如果它们有相同的条目，那么我们找到了一个子正方形。否则我们会尝试小1。
下面是上述想法的实现。
C++
// A C++ program to find the largest subsquare // surrounded by 'X' in a given matrix of 'O' and 'X' #include <iostream> using namespace std; // Size of given matrix is N X N #define N 6 // A utility function to find minimum of two numbers int getMin( int x, int y) { return (x < y) ? x : y; } // Returns size of maximum size subsquare matrix // surrounded by 'X' int findSubSquare( int mat[][N]) { int max = 0; // 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; } // Driver code 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' }, }; // Function call cout << findSubSquare(mat); return 0; } |
JAVA
// A JAVA program to find the // largest subsquare surrounded // by 'X' in a given matrix of // 'O' and 'X' import java.util.*; class GFG { // Size of given // matrix is N X N static int N = 6 ; // A utility function to // find minimum of two numbers static int getMin( int x, int y) { return (x < y) ? x : y; } // Returns size of maximum // size subsquare matrix // surrounded by 'X' static int findSubSquare( int mat[][]) { int max = 0 ; // Initialize result // Initialize the left-top // value in hor[][] and ver[][] int hor[][] = new int [N][N]; int ver[][] = new int [N][N]; hor[ 0 ][ 0 ] = ver[ 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 // subsquare 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; } // Driver Code public static void main(String[] args) { // TODO Auto-generated method stub 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' } }; // Function call System.out.println(findSubSquare(mat)); } } // This code is contributed // by ChitraNayal |
Python3
# A Python3 program to find the largest # subsquare surrounded by 'X' in a given # matrix of 'O' and 'X' import math as mt # Size of given matrix is N X N N = 6 # A utility function to find minimum # of two numbers def getMin(x, y): if x < y: return x else : return y # Returns size of Maximum size # subsquare matrix surrounded by 'X' def findSubSquare(mat): Max = 0 # Initialize result # Initialize the left-top value # in hor[][] and ver[][] hor = [[ 0 for i in range (N)] for i in range (N)] ver = [[ 0 for i in range (N)] for i in range (N)] if mat[ 0 ][ 0 ] = = 'X' : hor[ 0 ][ 0 ] = 1 ver[ 0 ][ 0 ] = 1 # Fill values in hor[][] and ver[][] for i in range (N): for j in range (N): if (mat[i][j] = = 'O' ): ver[i][j], hor[i][j] = 0 , 0 else : if j = = 0 : ver[i][j], hor[i][j] = 1 , 1 else : (ver[i][j], hor[i][j]) = (ver[i - 1 ][j] + 1 , hor[i][j - 1 ] + 1 ) # Start from the rightmost-bottommost corner # element and find the largest ssubsquare # with the help of hor[][] and ver[][] for i in range (N - 1 , 0 , - 1 ): for j in range (N - 1 , 0 , - 1 ): # Find smaller of values in hor[][] and # ver[][]. A Square can only be made by # taking smaller value 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 and hor[i - small + 1 ][j] > = small): Max = small small - = 1 return Max # Driver Code 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' ]] # Function call print (findSubSquare(mat)) # This code is contributed by # Mohit kumar 29 |
C#
// A C# program to find the // largest subsquare surrounded // by 'X' in a given matrix of // 'O' and 'X' using System; class GFG { // Size of given // matrix is N X N static int N = 6; // A utility function to // find minimum of two numbers static int getMin( int x, int y) { return (x < y) ? x : y; } // Returns size of maximum // size subsquare matrix // surrounded by 'X' static int findSubSquare( int [, ] mat) { int max = 0; // Initialize result // Initialize the left-top // value in hor[][] and ver[][] int [, ] hor = new int [N, N]; int [, ] ver = new int [N, N]; hor[0, 0] = ver[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 // subsquare 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; } // Driver Code public static void Main() { // TODO Auto-generated method stub 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' } }; // Function call Console.WriteLine(findSubSquare(mat)); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // A PHP 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 $N = 6; // A utility function to find // minimum of two numbers function getMin( $x , $y ) { return ( $x < $y ) ? $x : $y ; } // Returns size of maximum // size subsquare matrix // surrounded by 'X' function findSubSquare( $mat ) { $max = 0; // Initialize result $hor [0][0] = $ver [0][0] = ( $mat [0][0] == 'X' ); // Fill values in // $hor and $ver for ( $i = 0; $i < $GLOBALS [ 'N' ]; $i ++) { for ( $j = 0; $j < $GLOBALS [ '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 // subsquare with the help of // $hor and $ver for ( $i = $GLOBALS [ 'N' ] - 1; $i >= 1; $i --) { for ( $j = $GLOBALS [ 'N' ] - 1; $j >= 1; $j --) { // Find smaller of values in // $hor and $ver A Square can // only be made by taking // smaller value $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 ; } // Driver Code $mat = array ( array ( 'X' , 'O' , 'X' , 'X' , 'X' , 'X' ), array ( 'X' , 'O' , 'X' , 'X' , 'O' , 'X' ), array ( 'X' , 'X' , 'X' , 'O' , 'O' , 'X' ), array ( 'O' , 'X' , 'X' , 'X' , 'X' , 'X' ), array ( 'X' , 'X' , 'X' , 'O' , 'X' , 'O' ), array ( 'O' , 'O' , 'X' , 'O' , 'O' , 'O' )); // Function call echo findSubSquare( $mat ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // A JavaScript 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 let N = 6; // A utility function to // find minimum of two numbers function getMin(x,y) { return (x < y) ? x : y; } // Returns size of maximum // size subsquare matrix // surrounded by 'X' function findSubSquare(mat) { let max = 0; // Initialize result // Initialize the left-top // value in hor[][] and ver[][] let hor = new Array(N); let ver = new Array(N); for (let i = 0; i < N; i++) { hor[i]= new Array(N); ver[i]= new Array(N); for (let j = 0; j < N; j++) { hor[i][j]= "" ; ver[i][j]= "" ; } } hor[0][0] = 'X' ; ver[0][0] = 'X' ; // Fill values in // hor[][] and ver[][] for (let i = 0; i < N; i++) { for (let 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 // subsquare with the help // of hor[][] and ver[][] for (let i = N - 1; i >= 1; i--) { for (let j = N - 1; j >= 1; j--) { // Find smaller of values in // hor[][] and ver[][] A Square // can only be made by taking // smaller value let 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; } // Driver Code // TODO Auto-generated method stub let 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' ]] //Function call document.write(findSubSquare(mat)) // This code is contributed by unknown2108 </script> |
输出
4
优化方法：
一个更优化的解决方案是在一个名为 数据处理 现在，每一条 数据处理 我们有一对（int，int），它表示直到该点的最大连续“X”，即。
- dp[i][j]。第一个表示连续的“X”，水平移动到该点。
- dp[i][j]。第二个表示垂直于该点的连续“X”。
现在，可以用dp[i][j]作为右下角形成一个正方形，其边长为， min（dp[i][j]。第一，dp[i][j]。第二）
所以，我们制作另一个矩阵 麦克赛德 ，表示形成的最大方形边，其右下角为arr[i][j]。我们将尝试从正方形的性质中获得一些直觉，即正方形的所有边都是相等的。
让我们存储可以获得的最大值，如val=min（dp[i][j]。首先，dp[i][j]。第二）。从点（i，j）开始，我们水平向后移动距离Val，并检查最小垂直连续“X”，直到该点等于Val。
类似地，我们通过距离Val垂直向后移动，并检查最小水平连续“X”是否等于Val？在这里，我们利用了正方形的所有边都是相等的这一事实。
输入矩阵：
xOxXX
xOxOx
X X X O X
O X X X X X
X X X O X O
O O X O O
矩阵dp的值：
(1,1) (0,0) (1,1) (2,7) (3,1) (4,1)
(1,2) (0,0) (1,2) (2,8) (0,0) (1,2)
(1,3) (2,1) (3,3) (0,0) (0,0) (1,3)
(0,0) (1,2) (2,4) (3,1) (4,1) (5,4)
(1,1) (2,3) (3,5) (0,0) (1,2) (0,0)
(0,0) (0,0) (1,6) (0,0) (0,0) (0,0)
以下是上述理念的实施情况：
C++
// A C++ program to find the largest subsquare // surrounded by 'X' in a given matrix of 'O' and 'X' #include <bits/stdc++.h> using namespace std; // Size of given matrix is N X N #define N 6 int maximumSubSquare( int arr[][N]) { pair< int , int > dp[51][51]; int maxside[51][51]; // Initialize maxside with 0 memset (maxside, 0, sizeof (maxside)); int x = 0, y = 0; // Fill the dp matrix horizontally. // for contiguous 'X' increment the value of x, // otherwise make it 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; } } // Fill the dp matrix vertically. // For contiguous 'X' increment the value of y, // otherwise make it 0 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; } } // 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. 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; // store the final answer in maxval maxval = max(maxval, maxside[i][j]); } } // return the final answe. return maxval; } // Driver code 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' }, }; // Function call cout << maximumSubSquare(mat); return 0; } |
JAVA
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { static int N = 6 ; static int maximumSubSquare( int [][] arr) { int [][][] dp = new int [ 51 ][ 51 ][ 2 ]; int [][] maxside = new int [ 51 ][ 51 ]; // Initialize maxside with 0 for ( int [] row : maxside) Arrays.fill(row, 10 ); int x = 0 , y = 0 ; // Fill the dp matrix horizontally. // for contiguous 'X' increment the value of x, // otherwise make it 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; } } // Fill the dp matrix vertically. // For contiguous 'X' increment the value of y, // otherwise make it 0 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; } } // 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. 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 ; // store the final answer in maxval maxval = Math.max(maxval, maxside[i][j]); } } // return the final answe. return maxval; } // Driver code 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' }, }; // Function call System.out.println(maximumSubSquare(mat)); } } // This code is contributed by rag2127. |
Python3
# Python3 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 N = 6 def maximumSubSquare(arr): dp = [[[ - 1 , - 1 ] for i in range ( 51 )] for j in range ( 51 )] # Initialize maxside with 0 maxside = [[ 0 for i in range ( 51 )] for j in range ( 51 )] x = 0 y = 0 # Fill the dp matrix horizontally. # for contiguous 'X' increment the # value of x, otherwise make it 0 for i in range (N): x = 0 for j in range (N): if (arr[i][j] = = 'X' ): x + = 1 else : x = 0 dp[i][j][ 0 ] = x # Fill the dp matrix vertically. # For contiguous 'X' increment # the value of y, otherwise # make it 0 for i in range (N): for j in range (N): if (arr[j][i] = = 'X' ): y + = 1 else : y = 0 dp[j][i][ 1 ] = y # 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. maxval = 0 val = 0 for i in range (N): for j in range (N): val = min (dp[i][j][ 0 ], dp[i][j][ 1 ]) if (dp[i][j - val + 1 ][ 1 ] > = val and dp[i - val + 1 ][j][ 0 ] > = val): maxside[i][j] = val else : maxside[i][j] = 0 # Store the final answer in maxval maxval = max (maxval, maxside[i][j]) # Return the final answe. return maxval # Driver code 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' ] ] # Function call print (maximumSubSquare(mat)) # This code is contributed by avanitrachhadiya2155 |
C#
// A C# program to find the largest subsquare // surrounded by 'X' in a given matrix of 'O' and 'X' using System; public class GFG{ static int N = 6; static int maximumSubSquare( int [,] arr) { int [,,] dp = new int [51,51,2]; int [,] maxside = new int [51,51]; // Initialize maxside with 0 for ( int i = 0; i < 51; i++) { for ( int j = 0; j < 51; j++) { maxside[i,j] = 10; } } int x = 0, y = 0; // Fill the dp matrix horizontally. // for contiguous 'X' increment the value of x, // otherwise make it 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; } } // Fill the dp matrix vertically. // For contiguous 'X' increment the value of y, // otherwise make it 0 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; } } // 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. 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; // store the final answer in maxval maxval = Math.Max(maxval, maxside[i,j]); } } // return the final answe. return maxval; } // Driver code static public void Main (){ 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' }, }; // Function call Console.WriteLine(maximumSubSquare(mat)); } } // This code is contributed by patel2127 |
Javascript
<script> /*package whatever //do not write package name here */ let N = 6; function maximumSubSquare(arr) { let dp = new Array(51); for (let i = 0; i < 51; i++) { dp[i] = new Array(51); for (let j = 0; j < 51; j++) { dp[i][j] = new Array(2); for (let k = 0; k < 2; k++) { dp[i][j][k] = 0; } } } let maxside = new Array(51); for (let i = 0; i < 51; i++) { maxside[i] = new Array(51); for (let j = 0; j < 51; j++) { maxside[i][j] = 10; } } let x = 0, y = 0; // Fill the dp matrix horizontally. // for contiguous 'X' increment the value of x, // otherwise make it 0 for (let i = 0; i < N; i++) { x = 0; for (let j = 0; j < N; j++) { if (arr[i][j] == 'X' ) x += 1; else x = 0; dp[i][j][0] = x; } } // Fill the dp matrix vertically. // For contiguous 'X' increment the value of y, // otherwise make it 0 for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { if (arr[j][i] == 'X' ) y += 1; else y = 0; dp[j][i][1] = y; } } // 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. let maxval = 0, val = 0; for (let i = 0; i < N; i++) { for (let 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; // store the final answer in maxval maxval = Math.max(maxval, maxside[i][j]); } } // return the final answe. return maxval; } // Driver code let 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' ] ]; // Function call document.write(maximumSubSquare(mat)); // This code is contributed by ab2127 </script> |
输出
4
时间复杂性： O（N） 2. ) 辅助空间复杂性 ：O（N） 2. )
本文由 阿比纳夫·拉斯托吉 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
