Работа с матрицей из 0 и 1 [требует правки]

311

06 ноября 2017, 22:33

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

Не знаю, как действовать. Была идея "попросить" пользователя ввести количество строк и количество столбцов - тогда их произведение будет равно количеству всех элементов матрицы. Задать массив с количеством элементов (это произведение).

Дальше циклом for( ) "бежать" по строке и искать нули. Если 0 найден, прибавляем площади значение один. Если найден рядом 0 справа S+=1. Когда в строке кончаются нули - переходим на следующую строку к элементу I+n, где i - номер первого нуля. А n - количество элементов в строке (или количество столбцов). Подскажите как бы действовали вы?

Все до чего смог сейчас додуматься - это по циклам считываю лишь количество нулей в матрице

Answer 1

Считываем размерность матрицы n и m
Создаём матрицу а[n+1][m+1], можно векторами
Считываем значения пропустив первый столбец и первую строку
Создаём матрицу s[n+1][m+1], можно векторами
Заполняем первый столбец и первую строку нулями
Какдый элемент матрицы s должен содержать сумму всех элементов прямоугольника матрицы a от левого верхнего угла до текущих индексов
```
s[i][j] = sum { q in 1 to i } of sum { w in 1 to j } of a[q][w]
```
Но на самом деле обновляем так:
```
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]
```
Делаем 4 вложенных цикла (t, l, b, r - top, left, bottom, right) и проеверяем, что сумма элементов этого прямоугольника равна 0:
```
if (s[b][r] - s[t-1][r] - s[b][l-1] + s[t-1][l-1] == 0)
```
Среди равных выбираем с наибольшей площадью (b-t+1) * (r-l+1).
Стоит изначально подвинуть t и l на 1, чтобы везде не вычитать из них единицу.