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