Используя подход Greedy, учитывая булеву матрицу B размером m × n, найдите ее наибольшую квадратную подматрицу, все элементы которой равны нулю

Question

Кто-нибудь знает, используя жадный подход, пожалуйста, помогите мне решить эту проблему. Я уже сделал это с помощью динамического подхода. Но моя главная задача - использовать метод Жадность. А также мы должны найти максимальную квадратную подматрицу из 0. https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ Вот пример использования динамического подхода и поиска элементов, имеющих 1. ПРИМЕЧАНИЕ: используя жадный

Answer 1

Жадный подход - это когда вы делаете локально оптимальный выбор, полагая, что он приведет к оптимальному решению. Таким образом, в основном мы начинаем с поиска 0 в одном из четырех полей матрицы mXn, то есть в 1-й строке, последней строке, первом столбце или последнем столбце. Как только найден 0, мы начинаем с поиска максимально возможного квадрата.

Пример-

0 0 1 1 0 0

1 0 0 0 0 0

1 1 1 0 0 0

1 1 1 0 0 0

1 0 0 0 0 0

В приведенном выше примере первый элемент равен 0, поэтому проверьте наличие матрицы 5X5, она не работает, поскольку третий элемент равен 1. Сейчас есть несколько случаев -

1] Если вы оставите первый ряд для дальнейшей оценки, вы все равно можете стремиться к матрице размера 4X4.

2] Если вы покидаете третий столбец и рассматриваете только первые два столбца, нацеливайтесь на матрицу 2X2.

3] Если вы покидаете третий столбец и рассматриваете только последние три столбца, нацеливайтесь на матрицу 3X3.

4] Мы бы не рассматривали вариант удаления как строки, так и столбца, так как он был бы не лучше, чем предыдущие три варианта.

Учитывая жадность, мы бы выбрали 1-й случай и повторили процесс.