Комбинаторика 2

Описание работы

Описание работы

условие задачи

Землевладельцу нужна земля для покупки. Земля представляет из себя прямоугольное поле шириной n и высотой m, которое состоит из участков, где 1 - плодородный участок, а 0 – неплодородный. Землевладелец может либо купить регион поля любого размера, либо отказаться от покупки, если доступных для покупки регионов нет.

Условия покупки следующие:

• – Регион – это прямоугольник, ограничивающий соприкасающиеся участки плодородной почвы
• – Участки "соприкасаются" если они соседние друг для друга – сверху, снизу, справа, слева и по диагонали
• 1 0 1
• 0 1 1
• 1 0 1
• 0 0 0
• 0 1 0
• На примере выше соприкасаются все участки, кроме нижнего, то есть регионов здесь 2, один площадью 9, другой площадью 1
• – Регионы могут пересекаться между собой:
• 1 1 1 1 1
• 1 0 0 0 1
• 1 0 1 0 1
• Здесь тоже два региона, один площадью 15 (все поле), другой площадью 1
• – Минимальное количество плодородных участков в регионе для покупки – 2
• – Покупатель платит только за общую площадь купленного региона

Землевладелец хочет потратить деньги как можно оптимальнее – купить тот регион, в котором будет максимальное соотношение плодородной земли к общей площади региона. Если есть несколько регионов с одинаковой «эффективностью», то землевладелец хочет купить бóльший из них по площади.

Нужно определить площадь региона, который стоит купить фермеру

Входные данные (поступают в стандартный поток ввода)

Первая строка – целые числа n, m через пробел (2≤n≤100, 2≤m≤100)

Далее m строк, в каждой из которых по n цифр 0 или 1, разделенных пробелами

Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются

Выходные данные (ожидаются в стандартном потоке вывода)

Одно целое число, площадь наилучшего региона, или 0, в случае отказа от покупки

Пример 1

Ввод:

5 4

0 1 1 0 0

1 1 1 0 1

1 1 0 0 1

0 0 0 1 0

Вывод:

9

На этом поле доступны для покупки:

Первый регион для покупки

• Левый верхний угол с координатами [0, 0]
• Правый нижний угол с координатами [2, 2]

Его площадь 9, а плодородных участков на нем 7.

Эффективность покупки этого региона рассчитывается как 7/9

Второй регион поля для покупки

• Левый верхний угол с координатами [3, 1]
• Правый нижний угол с координатами [4, 3]

Его площадь 6, а плодородных участков на нем 3.

Эффективность покупки этого региона рассчитывается как 3/6

7/9 > 3/6, поэтому Василию стоит купить первый регион.

Пример 2

Ввод:

5 3

1 1 1 0 1

1 1 1 0 1

1 1 1 0 1

Вывод:

9

Здесь эффективность регионов одинакова – они оба полностью заполнены плодородной землей, но регион слева больше, поэтому ответ 9

добавлю от себя еще один тест:

3 3

1 1 0

1 0 0

1 0 1

вывод: 6

Примечания по оформлению решения

Возможно использование только стандартных библиотек языков, установки и использование дополнительных библиотек невозможны.

Проверка входных данных не требуется, все данные гарантированно соблюдают условия, указанные в разделе входные данные

Ограничение времени, с 1

Ограничение памяти, МБ 64

Нужно сделать на python!