Рубрики

Максимальный размер квадратной подматрицы со всеми 1

По заданной двоичной матрице определите квадратную подматрицу максимального размера со всеми единицами.

Например, рассмотрим приведенную ниже двоичную матрицу.

Алгоритм:
Пусть заданная бинарная матрица будет M [R] [C]. Идея алгоритма состоит в том, чтобы построить вспомогательную матрицу размеров S [] [], в которой каждая запись S [i] [j] представляет размер квадратной подматрицы со всеми 1, включая M [i] [j], где M [ i] [j] — самая правая и самая нижняя запись в подматрице.

1) Construct a sum matrix S[R][C] for the given M[R][C].
     a)    Copy first row and first columns as it is from M[][] to S[][]
     b)    For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print 
   sub-matrix of M[][]

Для данного M [R] [C] в вышеприведенном примере построенный S [R] [C] будет:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

Значение максимальной записи в приведенной выше матрице равно 3, а координаты записи равны (4, 3). Используя максимальное значение и его координаты, мы можем узнать необходимую подматрицу.

C ++

// C ++ код для квадрата максимального размера
// подматрица со всеми 1
#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; 

      

    / * Установить первый столбец S [] [] * /

    for(i = 0; i < R; i++) 

        S[i][0] = M[i][0]; 

      

    / * Установить первый ряд S [] [] * /

    for(j = 0; j < C; j++) 

        S[0][j] = M[0][j]; 

          

    / * Построить другие записи 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],min( S[i-1][j], 

                                S[i-1][j-1])) + 1; 

            else

                S[i][j] = 0; 

        

    

      

    / * Найти максимальную запись и индексы максимальной записи

        в 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"

    

  

  
/ * Код водителя * /

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); 

  
// Это код, предоставленный rathbhupendra

С

// код C для квадрата максимального размера
// подматрица со всеми 1
#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; 

  
/ * Установить первый столбец S [] [] * /

for(i = 0; i < R; i++)

    S[i][0] = M[i][0];

  

/ * Установить первый ряд S [] [] * /    

for(j = 0; j < C; j++)

    S[0][j] = M[0][j];

      
/ * Построить другие записи 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;

    

  
/ * Найти максимальную запись и индексы максимальной записи

    в 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");


}     

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для получения минимум трех значений * /

int min(int a, int b, int c)

{

int m = a;

if (m > b) 

    m = b;

if (m > c) 

    m = c;

return m;

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

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-код для квадрата максимального размера
// подматрица со всеми 1

public class GFG

{

    // метод для квадратной подматрицы максимального размера со всеми 1

    static void printMaxSubSquare(int M[][])

    {

        int i,j;

        int R = M.length;         // нет строк в M [] []

        int C = M[0].length;     // нет столбцов в M [] []

        int S[][] = new int[R][C];     

          

        int max_of_s, max_i, max_j; 

      

        / * Установить первый столбец S [] [] * /

        for(i = 0; i < R; i++)

            S[i][0] = M[i][0];

      

        / * Установить первый ряд S [] [] * /

        for(j = 0; j < C; j++)

            S[0][j] = M[0][j];

          

        / * Построить другие записи 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;

            

        }     

          

        / * Найти максимальную запись и индексы максимальной записи

            в 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();

        

    

      

    // Драйвер программы

    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 код для максимального размера
# квадратная подматрица со всеми 1

  

def printMaxSubSquare(M):

    R = len(M) № № строк в M [] []

    C = len(M[0]) № № столбцов в M [] []

  

    S = [[0 for k in range(C)] for l in range(R)]

    # здесь мы установили первую строку и столбец S [] []

  

    # Построить другие записи

    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

      

    # Найти максимальную запись и

    # индексы максимальной записи в 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("")

  
# Драйверная программа

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)

  
# Этот код предоставлен Soumen Ghosh

C #

// код C # для квадрата максимального размера
// подматрица со всеми 1

  

using System;

  

  

public class GFG

{

    // метод для квадратной подматрицы максимального размера со всеми 1

    static void printMaxSubSquare(int [,]M)

    {

        int i,j;

        // нет строк в M [,]

        int R = M.GetLength(0);    

         // нет столбцов в M [,]

        int C = M.GetLength(1);    

        int [,]S = new int[R,C];     

          

        int max_of_s, max_i, max_j; 

          

        / * Установить первый столбец S [,] * /

        for(i = 0; i < R; i++)

            S[i,0] = M[i,0];

          

        / * Установить первый ряд S [] [] * /

        for(j = 0; j < C; j++)

            S[0,j] = M[0,j];

              

        / * Построить другие записи 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;

            

        }     

          

        / * Найти максимальную запись и индексы

            максимальная запись в 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();

        

    

      

    // Драйвер программы

    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-код для квадрата максимального размера
// подматрица со всеми 1

  

function printMaxSubSquare($M, $R, $C

    $S = array(array()) ;

  

    / * Установить первый столбец S [] [] * /

    for($i = 0; $i < $R; $i++) 

        $S[$i][0] = $M[$i][0]; 

      

    / * Установить первый ряд S [] [] * /

    for($j = 0; $j < $C; $j++) 

        $S[0][$j] = $M[0][$j]; 

          

    / * Построить другие записи 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; 

        

    

      

    / * Найти максимальную запись и индексы

    максимальной записи в 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); 

  
// Этот код предоставлен Ryuga
?>


Выход:

Maximum size sub-matrix is: 
1 1 1 
1 1 1 
1 1 1 

Сложность времени: O (m * n), где m — количество строк, а n — количество столбцов в данной матрице.
Вспомогательное пространство: O (m * n), где m — количество строк, а n — количество столбцов в данной матрице.
Алгоритмическая парадигма: динамическое программирование

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Максимальный размер квадратной подматрицы со всеми 1

0.00 (0%) 0 votes