Subarray cuadrada de tamaño máximo con todos los 1

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *