Java задача - земля для покупки

КОНСОЛЬНОЕ ПРИЛОЖЕНИЕ НА JAVA.

Фермер Василий выбирает землю для покупки. Предмет торгов – прямоугольное поле шириной 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

– Покупатель платит только за общую площадь купленного региона

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

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