Доброго времени суток.
Решаю задачу, но идеи закончились. А именно не могу придумать,как пройтись по массиву. Прошу помощи или хотя бы накинуть идеи.
Фермер Василий выбирает землю для покупки. Предмет торгов – прямоугольное поле шириной 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
Denis Kolesnikov
35 уровень
Нужна помощь в решении задачи
Комментарии (28)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Максим
18 октября 2022, 14:44
Я сделяль
RegionsTest.java
В мейне тестик, переделать под условие о стандартном вводе/выводе, думаю, несложно
0
Mikhail
21 октября 2022, 09:44
Не проходит. Выпадает ошибка по достижению максимальной глубины рекурсии
0
Максим
21 октября 2022, 12:14
Упс, точняк.
Пофиксил, заменив рекурсию на цикл.
tnx, btw
0
Ramazan Khakimov
22 октября 2022, 19:15
Подскажите, пожалуйста, по методу findNeighbor.
Что за переменные border и index?
0
Максим
25 октября 2022, 11:19
index - это обыкновенный параметр цикла for. Так как i было занято :) (во внутренних циклах, которые были и в предыдущей версии метода).
К тому же он фактически используется как индекс пары значений (массив Integer) в ArrayList.
border - отмечает верхнюю "границу" фактически введенных в АггayList значений пар координат. По сути, он содержит значение, аналогичное возвращаемому методом .size(). border увеличивается всякий раз, как в list загружается координаты следующей ячейки. Я посчитал, что это будет "экономнее", чем вызывать .size() всякий раз, перед тем как мы проходимся по телу цикла.
Логика метода такова. Мы создаем ArrayList coordinates с массивами Integer из двух значений, первое из которых - номер строки (координата у) второй - номер ячейки в строке (координата х). В него сразу же добавляются координаты первой ячейки. которой присваевается значение count (переданное из метода findRegions()). Далее запускается цикл, который будет срабатывать столько раз. сколько мы занесем пар координат в coordinates. Для каждой пары координат(то есть для каждого плодородного участка) который уже был отмечен (то есть ему присвоили значение count) ищутся соседние участки, которые пока не отмечены. Они отмечаются, их координаты добавляются к coordinates. Таким образом, цикл завершается, когда у последних добавленных участков больше нет соседних плодородных участков, которые не были бы отмечены.
0
jenia0jenia
15 октября 2022, 10:23
У кого есть тесты, дайте на проверку , пожалуйста
0
Emin BagirovExpert
15 октября 2022, 13:54
найдешь если пошли мне тоже
0
Emin BagirovExpert
14 октября 2022, 19:08
Вроде код работает. Но мне не нравится, что приходится слишком часто пробегать по всей матрице. с большими матрицами это будет больно. но в условии вроде матрицы обещают не очень большими
https://github.com/Sturvi/farmersSplot.git
0
Anonymous #3003966
15 октября 2022, 10:15
5 3
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
Вывод: 3 - а ожидается 9
с 5 4
0 1 1 0 0
1 1 1 0 1
1 1 0 0 1
0 0 0 1 0 то же самое
0
Emin BagirovExpert
15 октября 2022, 13:54
Cлучайно ошибся в одной переменной при последних изменениях. исправил
0
Emin BagirovExpert
15 октября 2022, 13:59
+1
Anonymous #3102054
16 октября 2022, 15:56
Вроде должно быть 49
0
Emin BagirovExpert
16 октября 2022, 20:12
ты серьезно?
0
Anonymous #3102054
17 октября 2022, 17:57
ну если я правильно понимаю условие, то в регионе 7 на 7 - 17 единиц, эффективность 17/49~0,34, а в регионе 3 на 3, эффективность 1/3~0,33. Или неправильно?
0
Emin BagirovExpert
18 октября 2022, 07:03
блин а ведь реально. визуально так не казалось. исправил.)
Но задачу приняли и без этого
0
Anonymous #3102054
18 октября 2022, 08:51
то есть система приняла ответ с ошибкой?
0
Emin BagirovExpert
19 октября 2022, 00:06
Получается так
0
Anonymous #3189643
19 октября 2022, 23:28
Здравствуйте, а вот на таких примерах алгоритм совсем отказывается работать
10 11
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0 1
1 0 1 0 1 1 0 1 0 1
1 0 1 0 0 0 0 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
0
Mikhail
21 октября 2022, 09:44
Ссылка не открывается, если что
0
Leon JlEOH
11 октября 2022, 18:56
У меня вопрос плиз поясните ;
Извините что влезаю)))
Задача:
Java Syntax Zero, 6 уровень, 4 лекция
Удаляем одинаковые строки
https://javarush.com/quests/lectures/questsyntaxpro.level05.lecture03
Объясните пожалуйста: вижу необходимость дополнительной переменной temp как в первом варианте на моём скрине, объясняю для себя это тем что если одинаковая пара нашлась то string[i] равна null а мне вообще-то дальше с ней сравнивать надо однако второй вариант тоже работает правильно. Поясните отсутствие необходимости создавать доп переменную для записи туда искомого значения плиз
0
Anonymous #3003966
11 октября 2022, 14:05
Как успехи?
0
Denis Kolesnikov
12 октября 2022, 05:26
Пока без особых успехов.
На leetcode есть похожие про острова,пытаюсь переделать алгоритм под свою
0
Павел
10 октября 2022, 17:47
Как вариант искать непрерывную последовательность нулей, от одного края до другого. Она получается будет разделять регионы.
0
Emin BagirovExpert
10 октября 2022, 19:41
Не обязательно.
1 1 0 1 0
1 1 1 0 0
0 0 1 0 1
1 0 0 0 1
Тут нет последовательности 0 от края до края. но разделение происходит
0
Павел
10 октября 2022, 20:33
Ну как же, (0, 4) начало (3, 0) конец
0
Emin BagirovExpert
11 октября 2022, 02:50
А если
1 1 0 1 0
1 1 1 0 1
0 0 1 0 1
1 0 0 0 1
0
Павел
11 октября 2022, 05:32
(2,0) (3,1)
0
Павел
11 октября 2022, 06:19
Вот так от края до края не получается
1 1 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
Но последовательность какая то есть
0