Рубрики

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

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

Input :   0 1 1 0
          1 1 1 1
          1 1 1 1
          1 1 0 0

Output :  1 1 1 1
          1 1 1 1

Мы обсудили решение на основе динамического программирования для поиска наибольшего квадрата с 1 с .

В этом посте обсуждается интересный метод, который использует самый большой прямоугольник под гистограммой в качестве подпрограммы. Ниже приведены шаги. Идея состоит в том, чтобы обновить каждый столбец данной строки соответствующим столбцом предыдущей строки и найти наибольшую область гистограммы для этой строки.

Step 1: Find maximum area for row[0]
Step 2:
    for each row in 1 to N - 1
        for each column in that row
            if A[row][column] == 1
              update A[row][column] with
                A[row][column] += A[row - 1][column]
    find area for that row
    and update maximum area so far 

Иллюстрация:

step 1:    0 1 1 0  maximum area  = 2
step 2:
    row 1  1 2 2 1  area = 4, maximum area becomes 4
    row 2  2 3 3 2  area = 8, maximum area becomes 8
    row 3  3 4 0 0  area = 6, maximum area remains 8

Ниже приведена реализация. Настоятельно рекомендуется сначала сослаться на этот пост, так как большая часть кода взята оттуда.

C ++

// C ++ программа для поиска наибольшего прямоугольника со всеми 1
// в двоичной матрице
#include<bits/stdc++.h>

using namespace std;

  
// Строки и столбцы в матрице ввода
#define R 4
#define C 4

  
// Находит максимальную площадь под представленной гистограммой
// по гистограмме. Смотрите ниже статью для деталей.
// https://www.geeksforgeeks.org/largest-rectangle-under-histogram/amp/

int maxHist(int row[])

{

    // Создать пустой стек. Стек содержит индексы

    // исторический [массив] / бары, сохраненные в стеке, всегда

    // в порядке возрастания их высот.

    stack<int> result;

  

    int top_val;     // Вершина стека

  

    int max_area = 0; // Инициализируем максимальную площадь в текущем

                      // строка (или гистограмма)

  

    int area = 0;    // Инициализируем область с текущей вершиной

  

    // Выполнить все столбцы данной гистограммы (или строки)

    int i = 0;

    while (i < C)

    {

        // Если этот бар выше, чем бар в верхнем стеке,

        // помещаем его в стек

        if (result.empty() || row[result.top()] <= row[i])

            result.push(i++);

  

        else

        {

            // Если этот бар ниже вершины стека, то

            // вычисляем площадь прямоугольника с вершиной стека как

            // самая маленькая (или минимальная высота) полоса. «Я» это

            // 'правильный индекс' для вершины и элемента перед

            // вершина в стеке - «левый индекс»

            top_val = row[result.top()];

            result.pop();

            area = top_val * i;

  

            if (!result.empty())

                area = top_val * (i - result.top() - 1 );

            max_area = max(area, max_area);

        }

    }

  

    // Теперь выталкиваем оставшиеся бары из стека и вычисляем площадь

    // с каждым всплывающим столбцом в качестве наименьшего столбца

    while (!result.empty())

    {

        top_val = row[result.top()];

        result.pop();

        area = top_val * i;

        if (!result.empty())

            area = top_val * (i - result.top() - 1 );

  

        max_area = max(area, max_area);

    }

    return max_area;

}

  
// Возвращает область самого большого прямоугольника со всеми 1 в A [] []

int maxRectangle(int A[][C])

{

    // Вычисляем площадь для первой строки и инициализируем ее как

    // результат

    int result = maxHist(A[0]);

  

    // перебираем строку, чтобы найти максимальную прямоугольную область

    // рассматриваем каждую строку как гистограмму

    for (int i = 1; i < R; i++)

    {

  

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

  

            // если A [i] [j] равно 1, то добавляем A [i -1] [j]

            if (A[i][j]) A[i][j] += A[i - 1][j];

  

  

        // Обновить результат, если область с текущей строкой (как последняя строка)

        // прямоугольника) больше

        result = max(result, maxHist(A[i]));

    }

  

    return result;

}

  
// Код драйвера

int main()

{

    int A[][C] = { {0, 1, 1, 0},

                   {1, 1, 1, 1},

                   {1, 1, 1, 1},

                   {1, 1, 0, 0},

                 };

  

    cout << "Area of maximum rectangle is "

         << maxRectangle(A);

  

    return 0;

}

Джава

// Java программа для поиска наибольшего прямоугольника со всеми 1
// в двоичной матрице

import java.io.*;

import java.util.*;

   

class GFG 

{

    // Находит максимальную площадь под представленной гистограммой

    // по гистограмме. Смотрите ниже статью для деталей.

    // https://www.geeksforgeeks.org/largest-rectangle-under-histogram/amp/

    static int maxHist(int R,int C,int row[])

    {

        // Создать пустой стек. Стек содержит индексы

        // исторический [массив] / бары, сохраненные в стеке, всегда

        // в порядке возрастания их высот.

        Stack<Integer> result = new Stack<Integer>();

       

        int top_val;     // Вершина стека

       

        int max_area = 0; // Инициализируем максимальную площадь в текущем

                          // строка (или гистограмма)

       

        int area = 0;    // Инициализируем область с текущей вершиной

       

        // Выполнить все столбцы данной гистограммы (или строки)

        int i = 0;

        while (i < C)

        {

            // Если этот бар выше, чем бар в верхнем стеке,

            // помещаем его в стек

            if (result.empty() || row[result.peek()] <= row[i])

                result.push(i++);

       

            else

            {

                // Если этот бар ниже вершины стека, то

                // вычисляем площадь прямоугольника с вершиной стека как

                // самая маленькая (или минимальная высота) полоса. «Я» это

                // 'правильный индекс' для вершины и элемента перед

                // вершина в стеке - «левый индекс»

                top_val = row[result.peek()];

                result.pop();

                area = top_val * i;

       

                if (!result.empty())

                    area = top_val * (i - result.peek() - 1 );

                max_area = Math.max(area, max_area);

            }

        }

       

        // Теперь вытолкните оставшиеся бары из стека и вычислите

        // область с каждым вытянутым столбцом в качестве наименьшего столбца

        while (!result.empty())

        {

            top_val = row[result.peek()];

            result.pop();

            area = top_val * i;

            if (!result.empty())

                area = top_val * (i - result.peek() - 1 );

       

            max_area = Math.max(area, max_area);

        }

        return max_area;

    }

  

    // Возвращает область наибольшего прямоугольника со всеми 1 в

    // A [] []

    static int maxRectangle(int R,int C,int A[][])

    {

        // Вычисляем площадь для первой строки и инициализируем ее как

        // результат

        int result = maxHist(R,C,A[0]);

       

        // перебираем строку, чтобы найти максимальную прямоугольную область

        // рассматриваем каждую строку как гистограмму

        for (int i = 1; i < R; i++)

        {

       

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

       

                // если A [i] [j] равно 1, то добавляем A [i -1] [j]

                if (A[i][j] == 1) A[i][j] += A[i - 1][j];

       

       

            // Обновить результат, если область с текущей строкой (как последняя

            // строка прямоугольника) больше

            result = Math.max(result, maxHist(R,C,A[i]));

        }

       

        return result;

    }

       

    // Код драйвера

    public static void main (String[] args) 

    {

        int R = 4;

        int C = 4;

  

        int A[][] = { {0, 1, 1, 0},

                      {1, 1, 1, 1},

                      {1, 1, 1, 1},

                      {1, 1, 0, 0},

                    };

        System.out.print("Area of maximum rectangle is "

                                  maxRectangle(R,C,A));

    }

}

   
// Предоставлено Пракрити Гупта

python3

# Python3 программа для поиска наибольшего прямоугольника
# со всеми 1 в двоичной матрице

  
# Строки и столбцы в матрице ввода

R = 4

C = 4

  
# Находит максимальную площадь под представленной гистограммой
# по гистограмме. Смотрите ниже статью для деталей.
# https: # www.geeksforgeeks.org / самый большой прямоугольник под гистограммой /

def maxHist(row):

  

    # Создать пустой стек. Стек держит

    # индексы исторического массива / сохраненные бары

    # в стеке всегда в порядке возрастания

    # их высоты.

    result = []

  

    top_val = 0     # Верх стека

  

    max_area = 0 # Инициализировать максимальную площадь в текущем

                 # строка (или гистограмма)

  

    area = 0 # Инициализировать область с текущей вершиной

  

    # Пройти через все бары данного

    # гистограмма (или строка)

    i = 0

    while (i < C): 

      

        # Если этот бар выше, чем

        # бар на верхнем стеке, поместите его в стек

        if (len(result) == 0) or (row[result[0]] <= row[i]):

            result.append(i)

            i += 1

        else:

          

            # Если этот бар ниже вершины стека,

            # затем рассчитать площадь прямоугольника с

            # вершина стека как наименьшая (или минимальная

            # высота) бар. «Я» является «правильный индекс» для

            # вершина и элемент перед вершиной в стеке

            # это «левый индекс»

            top_val = row[result[0]] 

            result.pop(0

            area = top_val *

  

            if (len(result)):

                area = top_val * (i - result[0] - 1

            max_area = max(area, max_area) 

          

    # Теперь вытолкните оставшиеся бары из стека

    # и рассчитать площадь с каждым совали

    # бар как самый маленький бар

    while (len(result)):

        top_val = row[result[0]] 

        result.pop(0

        area = top_val *

        if (len(result)): 

            area = top_val * (i - result[0] - 1

  

        max_area = max(area, max_area) 

      

    return max_area 

  
# Возвращает площадь наибольшего прямоугольника
# со всеми 1 в А

def maxRectangle(A):

      

    # Рассчитать площадь для первого ряда и

    # инициализировать его как результат

    result = maxHist(A[0]) 

  

    # перебрать строку, чтобы найти максимум прямоугольника

    # область, рассматривающая каждую строку как гистограмму

    for i in range(1, R):

      

        for j in range(C):

  

            # если A [i] [j] равен 1, тогда добавьте A [i -1] [j]

            if (A[i][j]):

                A[i][j] += A[i - 1][j] 

  

        # Обновить результат, если область с текущим

        # строка (как последняя строка) прямоугольника) больше

        result = max(result, maxHist(A[i])) 

      

    return result 

      
Код водителя

if __name__ == '__main__':

    A = [[0, 1, 1, 0],

         [1, 1, 1, 1], 

         [1, 1, 1, 1], 

         [1, 1, 0, 0]] 

  

    print("Area of maximum rectangle is"

                         maxRectangle(A))

      
# Этот код добавлен
# от SHUBHAMSINGH10

C #

// C # программа для поиска наибольшего прямоугольника
// со всеми единицами в двоичной матрице

using System;

using System.Collections.Generic;

  

class GFG

{
// Находит максимальную площадь под
// гистограмма представлена гистограммой.
// Подробности смотрите ниже в статье.
// https://www.geeksforgeeks.org/largest-rectangle-under-histogram/amp/

public static int maxHist(int R, int C, 

                          int[] row)

{

    // Создать пустой стек. Стек

    // содержит индексы массива hist [].

    // Бары хранятся в стеке всегда

    // в порядке возрастания их высот.

    Stack<int> result = new Stack<int>();

  

    int top_val; // Вершина стека

  

    int max_area = 0; // Инициализируем максимальную площадь в

                      // текущая строка (или гистограмма)

  

    int area = 0; // Инициализируем область с

                  // текущая вершина

  

    // Пробежаться по всем барам

    // заданная гистограмма (или строка)

    int i = 0;

    while (i < C)

    {

        // Если этот бар выше чем

        // бар на верхнем стеке, толкаем его в стек

        if (result.Count == 0 || 

            row[result.Peek()] <= row[i])

        {

            result.Push(i++);

        }

  

        else

        {

            // Если этот бар ниже верхнего

            // стека, затем вычислить площадь

            // прямоугольник с вершиной стека как

            // наименьшая (или минимальная высота)

            // бар. «Я» является «правильный индекс» для

            // верх и элемент перед

            // вершина в стеке - «левый индекс»

            top_val = row[result.Peek()];

            result.Pop();

            area = top_val * i;

  

            if (result.Count > 0)

            {

                area = top_val * (i - result.Peek() - 1);

            }

            max_area = Math.Max(area, max_area);

        }

    }

  

    // Теперь выталкиваем оставшиеся бары из

    // складываем и вычисляем площадь с

    // каждый вытолкнутый бар как самый маленький бар

    while (result.Count > 0)

    {

        top_val = row[result.Peek()];

        result.Pop();

        area = top_val * i;

        if (result.Count > 0)

        {

            area = top_val * (i - result.Peek() - 1);

        }

  

        max_area = Math.Max(area, max_area);

    }

    return max_area;

}

  
// Возвращает область наибольшего
// прямоугольник со всеми 1 в A [] []

public static int maxRectangle(int R, int C,    

                               int[][] A)

{

    // Расчет площади для первого ряда

    // и инициализируем его как результат

    int result = maxHist(R, C, A[0]);

  

    // перебрать строку, чтобы найти

    // максимальная прямоугольная площадь

    // рассматриваем каждую строку как гистограмму

    for (int i = 1; i < R; i++)

    {

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

        {

  

            // если A [i] [j] равен 1, то

            // добавляем A [i -1] [j]

            if (A[i][j] == 1)

            {

                A[i][j] += A[i - 1][j];

            }

        }

  

        // Обновить результат, если область с текущим

        // строка (как последняя строка прямоугольника) больше

        result = Math.Max(result, maxHist(R, C, A[i]));

    }

  

    return result;

}

  
// Код драйвера

public static void Main(string[] args)

{

    int R = 4;

    int C = 4;

  

    int[][] A = new int[][]

    {

        new int[] {0, 1, 1, 0},

        new int[] {1, 1, 1, 1},

        new int[] {1, 1, 1, 1},

        new int[] {1, 1, 0, 0}

    };

    Console.Write("Area of maximum rectangle is "

                            maxRectangle(R, C, A));

}
}

  
// Этот код предоставлен Shrikant13


Выход :

Area of maximum rectangle is 8


Сложность времени:
O (R x X)

Эта статья предоставлена Сандживом Кумаром. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

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

0.00 (0%) 0 votes