Добрый вечер,
Подскажите пожалуйсто с алгоритмом решения здачи:
"
Строительная компания приобрела участок земли прямоугольное поле размером N Ч M сек-
торов. После проведения геологических исследований выяснилось, что на поле есть K непригодных
для строительства секторов. Необходимо построить одно здание прямоугольной формы со сторо-
нами параллельными границам участка. Компания заинтересована в рациональном использовании
участка, поэтому границы здания должны упираться либо в непригодные для строительства секто-
ры, либо в границы участка. Сколько существует вариантов выбора места для строительства здания
на приобретенном участке?
Формат входного файла
В первой строке задаются размеры поля N, M (1 ≤ N, M ≤ 109) и количество непригодных
для строительства секторов K (1 ≤ K ≤ 500). В следующих K строках задаются координаты
непригодных секторов Xi, Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M). Все числа во входных данных целые.
Формат выходного файла
Число вариантов выбора места для строительства здания.
из мыслей:
например определим матрицу, в этой матрице по координатам определим бракованные участки.
проходя по каждой строке,смотрим если ячейка не совпадает с брак.учтаском идем дальше, копим инфу, дошли до конца матрицы переходим на новую строку так считаем, нужно также анализировать стобцы....что-то голова пухнет
Вопрос два: нужно максимизировать размер "здания" (и посчитать количество размещений такого здания), или нужно посчитать все возможные варианты размещения "зданий" любых размеров?
AndreTMВопрос два: нужно максимизировать размер "здания" (и посчитать количество размещений такого здания), или нужно посчитать все возможные варианты размещения "зданий" любых размеров?
Постановка хреновая, а спрашивается, думаю, примерно следующее: если, начиная с каждой "клеточки" по очереди, расширять "здание" в каждую сторону до упора, то сколько разных прямоугольников будет получено?
0) нет ни одного плохого участка : ответ = 1 (вариант)
1) добавляем первый плохой участок : ответ (в общем случае) = 4 (варианта)
2) добавляем второй плохой участок
на каждом шаге поддерживаем список получившихся зданий
Потом добавляем следующий плохой участок и смотрим как он рубит какие-то здания
из предыдущего списка зданий
Про размеры здания непонятно...
Как минимум, есть (M * N - K) возможностей построить здание размером в один сектор. Потом еще куча вариантов для строительства зданий размером в два сектора. При M и N чуть больше 25 и К = 500 вариантов будет мало, при M и N, близких к 100, и К, близких к 1, ответ будет огромный.
Секторы квадратные?
rockclimberПро размеры здания непонятно...
Как минимум, есть (M * N - K) возможностей построить здание размером в один сектор.авторграницы здания должны упираться либо в непригодные для строительства секторы, либо в границы участка.Все границы, очевидно.
AbstractionВсе границы, очевидно.То есть надо найти в той части, что осталось после выкидывания непригодных участков, куски, которые прямоугольные (а не в виде блоков из тетриса)?
denis_stellграницы здания должны упираться либо в непригодные для строительства секторы, либо в границы участкаЭто означает "Граница здания в КАДЖОЙ точке должна упираться либо в непригодные для строительства секторы, либо в границы участка" или "Каждая сторона здания ХОТЯ БЫ В ОДНОЙ точке должна упираться либо в непригодные для строительства секторы, либо в границы участка"?
---Rt--------Ну совершенно же четкая и ясная постановка задачи.
Я не понимаю как ее можно не понимать.......
Человек интуитивно понимает, что размеры здания имеют гораздо большее практическое значение, нежели упор в загадочные "непригодные участки", и компания, заинтересованная в рациональном использовании чего бы то ни было, просто не может рассматривать здание 3x5 и здание 30x50 как объекты одного класса (возможные варианты решения одной и той же задачи).
---Rt--------под плохим сектором тут имеется в виду типа : в этом месте растет 100-летний дуб и спиливать его нельзя.
Но можно построить вокруг него зимний сад или внутренний дворик.
softwarer---Rt--------под плохим сектором тут имеется в виду типа : в этом месте растет 100-летний дуб и спиливать его нельзя.
Но можно построить вокруг него зимний сад или внутренний дворик.
или шикарный ночной бар =)
softwarerAndreTMВопрос два: нужно максимизировать размер "здания" (и посчитать количество размещений такого здания), или нужно посчитать все возможные варианты размещения "зданий" любых размеров?
Постановка хреновая, а спрашивается, думаю, примерно следующее: если, начиная с каждой "клеточки" по очереди, расширять "здание" в каждую сторону до упора, то сколько разных прямоугольников будет получено?
по идее, так, но мы идем горизонтально, например с слева направо.
если клетка "в пригодном секторе-ячейки" идем дальше, если нет запоминаем.
нужно и вертикально считать.
denis_stellПостановка нормальная, но алгоритм не могу составить.
Я вот одного не могу понять: здания должны быть прямоугольниками?
Меня смутили твои слова : "... произвольной формы"
denis_stellно алгоритм не могу составить.
не переживай по этому пункту
У меня есть в запасе штук 20 задач, которые я годами не могу решить
Всё нормально, человек не может вот всё решить
Ты ж наверняка студень, а мне уже скоро 49 лет
denis_stellздание - размер произвольной формы Хорошее выражение... "сфэрический куб"
denis_stellграницы здания должны упираться либо в непригодные для строительства секто-
ры, либо в границы участкаА, понял - действительно, при таком условии нужно именно максимизировать размер "здания"-прямоугольника, по месту расположения.
На самом деле, существует достаточно простое решение "в лоб":
- принимаем границы участка как "непригодные сектора"
- проходим по всем "пригодным" секторам; для входа в суммирование - текущий сектор должен быть верхним левым углом "здания" (для этого сектор должен граничить с "непригодными" слева и сверху)
-- подсчитываем количество возможных "зданий" в данной позиции (правый нижний угол должен граничить с "непригодными" справа и снизу )
А далее думаем и оптимизируем... Хотел я было ДП прикрутить, но затем немного подумал...
AndreTM- проходим по всем "пригодным" секторам; для входа в суммирование - текущий сектор должен быть верхним левым углом "здания" (для этого сектор должен граничить с "непригодными" слева и сверху)
-- подсчитываем количество возможных "зданий" в данной позиции (правый нижний угол должен граничить с "непригодными" справа и снизу )
А далее думаем и оптимизируем... Хотел я было ДП прикрутить, но затем немного подумал...Пусть у нас участок 5х5, один непригодный сектор ровно в центре. По-Вашему, требуемых строений на участке не будет вообще, а на самом деле их целых 4 штуки.
---Rt--------denis_stellно алгоритм не могу составить.
не переживай по этому пункту
У меня есть в запасе штук 20 задач, которые я годами не могу решить
Всё нормально, человек не может вот всё решить
Ты ж наверняка студень, а мне уже скоро 49 лет
Ну ты и старичелло, браза. Скоро уже пенсию
приносить будут а ты всё на ПТ....
Все поле это один прямоугольник N на M. L - список, который содержит пригодные участки. Вначале он стоит из всего участка.
1) Берем первый непригодный участок. В соответствие с ним разбиваем (NxM) на нужно число частей. И добавляем полученные участки пригодные в L, удалив из него NxM.
2) Берем следующий непригодный участок. Находим какие он затрагивает участки из L и разбиваем их также как на шаге 1.
Дальше снова 2. До тех пор, пока не закончатся непригодные участки.
На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых
сервисов с использованием метрической программы Яндекс.Метрика.
Продолжая использовать сайт, вы даёте согласие на обработку файлов cookie, необходимых для работы сайта. Другие опции вы можете выбрать по своему усмотрению.
По нижеприведенным ссылкам мы можете ознакомиться с действующим на сайте пользовательским соглашением и политикой конфиденциальности.
