Dada una array binaria, encuentre la subarray cuadrada de tamaño máximo con todos 1.
Por ejemplo, considere la siguiente array binaria.
C++
// C++ code for Maximum size square // sub-matrix with all 1s #include <bits/stdc++.h> #define bool int #define R 6 #define C 5 using namespace std; void printMaxSubSquare(bool M[R][C]) { int i,j; int S[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = min({S[i][j-1], S[i-1][j], S[i-1][j-1]}) + 1; //better of using min in case of arguments more than 2 else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } cout<<"Maximum size sub-matrix is: \n"; for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { cout << M[i][j] << " "; } cout << "\n"; } } /* Driver code */ int main() { bool M[R][C] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } // This code is contributed by rathbhupendra
C
// C code for Maximum size square // sub-matrix with all 1s #include<stdio.h> #define bool int #define R 6 #define C 5 void printMaxSubSquare(bool M[R][C]) { int i,j; int S[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } printf("Maximum size sub-matrix is: \n"); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { printf("%d ", M[i][j]); } printf("\n"); } } /* UTILITY FUNCTIONS */ /* Function to get minimum of three values */ int min(int a, int b, int c) { int m = a; if (m > b) m = b; if (m > c) m = c; return m; } /* Driver function to test above functions */ int main() { bool M[R][C] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); getchar(); }
Java
// JAVA Code for Maximum size square // sub-matrix with all 1s public class GFG { // method for Maximum size square sub-matrix with all 1s static void printMaxSubSquare(int M[][]) { int i,j; int R = M.length; //no of rows in M[][] int C = M[0].length; //no of columns in M[][] int S[][] = new int[R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = Math.min(S[i][j-1], Math.min(S[i-1][j], S[i-1][j-1])) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } System.out.println("Maximum size sub-matrix is: "); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { System.out.print(M[i][j] + " "); } System.out.println(); } } // Driver program public static void main(String[] args) { int M[][] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } }
Python3
# Python3 code for Maximum size # square sub-matrix with all 1s def printMaxSubSquare(M): R = len(M) # no. of rows in M[][] C = len(M[0]) # no. of columns in M[][] S = [] for i in range(R): temp = [] for j in range(C): if i==0 or j==0: temp += M[i][j], else: temp += 0, S += temp, # here we have set the first row and first column of S same as input matrix, other entries are set to 0 # Update other entries for i in range(1, R): for j in range(1, C): if (M[i][j] == 1): S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 else: S[i][j] = 0 # Find the maximum entry and # indices of maximum entry in S[][] max_of_s = S[0][0] max_i = 0 max_j = 0 for i in range(R): for j in range(C): if (max_of_s < S[i][j]): max_of_s = S[i][j] max_i = i max_j = j print("Maximum size sub-matrix is: ") for i in range(max_i, max_i - max_of_s, -1): for j in range(max_j, max_j - max_of_s, -1): print (M[i][j], end = " ") print("") # Driver Program M = [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]] printMaxSubSquare(M) # This code is contributed by Soumen Ghosh
C#
// C# Code for Maximum size square // sub-matrix with all 1s using System; public class GFG { // method for Maximum size square sub-matrix with all 1s static void printMaxSubSquare(int [,]M) { int i,j; //no of rows in M[,] int R = M.GetLength(0); //no of columns in M[,] int C = M.GetLength(1); int [,]S = new int[R,C]; int max_of_s, max_i, max_j; /* Set first column of S[,]*/ for(i = 0; i < R; i++) S[i,0] = M[i,0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0,j] = M[0,j]; /* Construct other entries of S[,]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i,j] == 1) S[i,j] = Math.Min(S[i,j-1], Math.Min(S[i-1,j], S[i-1,j-1])) + 1; else S[i,j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[,] */ max_of_s = S[0,0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i,j]) { max_of_s = S[i,j]; max_i = i; max_j = j; } } } Console.WriteLine("Maximum size sub-matrix is: "); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { Console.Write(M[i,j] + " "); } Console.WriteLine(); } } // Driver program public static void Main() { int [,]M = new int[6,5]{{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } }
PHP
<?php // PHP code for Maximum size square // sub-matrix with all 1s function printMaxSubSquare($M, $R, $C) { $S = array(array()) ; /* Set first column of S[][]*/ for($i = 0; $i < $R; $i++) $S[$i][0] = $M[$i][0]; /* Set first row of S[][]*/ for($j = 0; $j < $C; $j++) $S[0][$j] = $M[0][$j]; /* Construct other entries of S[][]*/ for($i = 1; $i < $R; $i++) { for($j = 1; $j < $C; $j++) { if($M[$i][$j] == 1) $S[$i][$j] = min($S[$i][$j - 1], $S[$i - 1][$j], $S[$i - 1][$j - 1]) + 1; else $S[$i][$j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ $max_of_s = $S[0][0]; $max_i = 0; $max_j = 0; for($i = 0; $i < $R; $i++) { for($j = 0; $j < $C; $j++) { if($max_of_s < $S[$i][$j]) { $max_of_s = $S[$i][$j]; $max_i = $i; $max_j = $j; } } } printf("Maximum size sub-matrix is: \n"); for($i = $max_i; $i > $max_i - $max_of_s; $i--) { for($j = $max_j; $j > $max_j - $max_of_s; $j--) { echo $M[$i][$j], " " ; } echo "\n" ; } } # Driver code $M = array(array(0, 1, 1, 0, 1), array(1, 1, 0, 1, 0), array(0, 1, 1, 1, 0), array(1, 1, 1, 1, 0), array(1, 1, 1, 1, 1), array(0, 0, 0, 0, 0)); $R = 6 ; $C = 5 ; printMaxSubSquare($M, $R, $C); // This code is contributed by Ryuga ?>
Javascript
<script> // JavaScript code for Maximum size square // sub-matrix with all 1s let R = 6; let C = 5; function printMaxSubSquare(M) { let i,j; let S = []; for ( var y = 0; y < R; y++ ) { S[ y ] = []; for ( var x = 0; x < C; x++ ) { S[ y ][ x ] = 0; } } let max_of_s, max_i, max_j; /* Set first column of S[][]*/ for(i = 0; i < R; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < C; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < R; i++) { for(j = 1; j < C; j++) { if(M[i][j] == 1) S[i][j] = Math.min(S[i][j-1],Math.min( S[i-1][j], S[i-1][j-1])) + 1; else S[i][j] = 0; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < R; i++) { for(j = 0; j < C; j++) { if(max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } document.write("Maximum size sub-matrix is: <br>"); for(i = max_i; i > max_i - max_of_s; i--) { for(j = max_j; j > max_j - max_of_s; j--) { document.write( M[i][j] , " "); } document.write("<br>"); } } /* Driver code */ let M = [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]; printMaxSubSquare(M); </script>
C++
// C++ code for Maximum size square // sub-matrix with all 1s // (space optimized solution) #include <bits/stdc++.h> using namespace std; #define R 6 #define C 5 void printMaxSubSquare(bool M[R][C]) { int S[2][C], Max = 0; // set all elements of S to 0 first memset(S, 0, sizeof(S)); // Construct the entries for (int i = 0; i < R;i++) for (int j = 0; j < C;j++){ // Compute the entrie at the current position int Entrie = M[i][j]; if(Entrie) if(j) Entrie = 1 + min(S[1][j - 1], min(S[0][j - 1], S[1][j])); // Save the last entrie and add the new one S[0][j] = S[1][j]; S[1][j] = Entrie; // Keep track of the max square length Max = max(Max, Entrie); } // Print the square cout << "Maximum size sub-matrix is: \n"; for (int i = 0; i < Max; i++, cout << '\n') for (int j = 0; j < Max;j++) cout << "1 "; } // Driver code int main () { bool M[R][C] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); return 0; // This code is contributed // by Gatea David }
Java
// Java program for the above approach import java.util.*; class GFG { static int R = 6 ; static int C = 5 ; static void printMaxSubSquare(int M[][]) { int S[][] = new int[2][C], Max = 0; // set all elements of S to 0 first for (int i = 0; i < 2;i++){ for (int j = 0; j < C;j++){ S[i][j] =0; } } // Construct the entries for (int i = 0; i < R; i++){ for (int j = 0; j < C; j++){ // Compute the entrie at the current position int Entrie = M[i][j]; if(Entrie != 0){ if(j != 0){ Entrie = 1 + Math.min(S[1][j - 1], Math.min(S[0][j - 1], S[1][j]));}} // Save the last entrie and add the new one S[0][j] = S[1][j]; S[1][j] = Entrie; // Keep track of the max square length Max = Math.max(Max, Entrie); } } // Print the square System.out.print("Maximum size sub-matrix is: \n"); for (int i = 0; i < Max; i++){ for (int j = 0; j < Max;j++){ System.out.print( "1 ");} System.out.println(); } } // Driver Code public static void main(String[] args) { int M[][] = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } } // This code is contributed by code_hunt.
Javascript
<script> // JavaScript code for Maximum size square // sub-matrix with all 1s // (space optimized solution) const R = 6 const C = 5 function printMaxSubSquare(M) { let Max = 0 let S = new Array(2) // set all elements of S to 0 first for(let i=0;i<2;i++){ S[i] = new Array(C).fill(0) } // Construct the entries for (let i = 0; i < R;i++) for (let j = 0; j < C;j++){ // Compute the entrie at the current position let Entrie = M[i][j]; if(Entrie) if(j) Entrie = 1 + Math.min(S[1][j - 1], Math.min(S[0][j - 1], S[1][j])); // Save the last entrie and add the new one S[0][j] = S[1][j]; S[1][j] = Entrie; // Keep track of the max square length Max = Math.max(Max, Entrie); } // Print the square document.write("Maximum size sub-matrix is: ","</br>") for (let i = 0; i < Max; i++){ for (let j = 0; j < Max;j++) document.write("1 ") document.write("</br>") } } // Driver code const M = [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]] printMaxSubSquare(M) // This code is contributed by shinjanpatra </script>
Python3
# Python code for Maximum size square # sub-matrix with all 1s # (space optimized solution) R = 6 C = 5 def printMaxSubSquare(M): global R,C Max = 0 # set all elements of S to 0 first S = [[0 for col in range(C)]for row in range(2)] # Construct the entries for i in range(R): for j in range(C): # Compute the entrie at the current position Entrie = M[i][j] if(Entrie): if(j): Entrie = 1 + min(S[1][j - 1],min(S[0][j - 1], S[1][j])) # Save the last entrie and add the new one S[0][j] = S[1][j] S[1][j] = Entrie # Keep track of the max square length Max = max(Max, Entrie) # Print the square print("Maximum size sub-matrix is: ") for i in range(Max): for j in range(Max): print("1",end=" ") print() # Driver code M = [[0, 1, 1, 0, 1], [1, 1, 0, 1, 0], [0, 1, 1, 1, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]] printMaxSubSquare(M) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach using System; using System.Numerics; using System.Collections.Generic; public class GFG { static int R = 6 ; static int C = 5 ; static void printMaxSubSquare(int[,] M) { int[,] S = new int[2, C]; int Maxx = 0; // set all elements of S to 0 first for (int i = 0; i < 2;i++){ for (int j = 0; j < C;j++){ S[i, j] =0; } } // Construct the entries for (int i = 0; i < R; i++){ for (int j = 0; j < C; j++){ // Compute the entrie at the current position int Entrie = M[i, j]; if(Entrie != 0){ if(j != 0){ Entrie = 1 + Math.Min(S[1, j - 1], Math.Min(S[0, j - 1], S[1, j]));}} // Save the last entrie and add the new one S[0,j] = S[1,j]; S[1,j] = Entrie; // Keep track of the max square length Maxx = Math.Max(Maxx, Entrie); } } // Print the square Console.Write("Maximum size sub-matrix is: \n"); for (int i = 0; i < Maxx; i++){ for (int j = 0; j < Maxx;j++){ Console.Write( "1 ");} Console.WriteLine(); } } // Driver Code public static void Main(string[] args) { int[,] M = {{0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 0}}; printMaxSubSquare(M); } }
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA