Добрый вечер,
Подскажите пожалуйсто с алгоритмом решения здачи:
"
Строительная компания приобрела участок земли прямоугольное поле размером N Ч M сек-
торов. После проведения геологических исследований выяснилось, что на поле есть K непригодных
для строительства секторов. Необходимо построить одно здание прямоугольной формы со сторо-
нами параллельными границам участка. Компания заинтересована в рациональном использовании
участка, поэтому границы здания должны упираться либо в непригодные для строительства секто-
ры, либо в границы участка. Сколько существует вариантов выбора места для строительства здания
на приобретенном участке?
Формат входного файла
В первой строке задаются размеры поля N, M (1 ≤ N, M ≤ 109) и количество непригодных
для строительства секторов K (1 ≤ K ≤ 500). В следующих K строках задаются координаты
непригодных секторов Xi, Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M). Все числа во входных данных целые.
Формат выходного файла
Число вариантов выбора места для строительства здания.

"

из мыслей:
например определим матрицу, в этой матрице по координатам определим бракованные участки.
проходя по каждой строке,смотрим если ячейка не совпадает с брак.учтаском идем дальше, копим инфу, дошли до конца матрицы переходим на новую строку так считаем, нужно также анализировать стобцы....что-то голова пухнет

AndreTM,
здание - размер произвольной формы
интересует количество размещений таких зданий

softwarerAndreTMВопрос два: нужно максимизировать размер "здания" (и посчитать количество размещений такого здания), или нужно посчитать все возможные варианты размещения "зданий" любых размеров?
Постановка хреновая, а спрашивается, думаю, примерно следующее: если, начиная с каждой "клеточки" по очереди, расширять "здание" в каждую сторону до упора, то сколько разных прямоугольников будет получено?


по идее, так, но мы идем горизонтально, например с слева направо.
если клетка "в пригодном секторе-ячейки" идем дальше, если нет запоминаем.
нужно и вертикально считать.

---Rt--------Ну совершенно же четкая и ясная постановка задачи.
Я не понимаю как ее можно не понимать.......

Постановка нормальная, но алгоритм не могу составить.

я так понимаю.

softwarer,

полностью согласен, ошибся.
нужно построить одно здание

ребят,ну подскажите как подсчитать?
сделал так:
ввел матрицу, в дэволтном значении все значения матрицы =1
затем спрашиваю у ползователя "введи сколько не пригодных участков"
вводим
затем,в зависимости от того сколько участков, вводим для каждого участка координаты
после того как определили координаты - заменяем эти значения 0
т.е. 1 пригодный участок. 0 не пригодный
получается что-то типа этого:
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
1 0 1 0 1
допустим так, потом например иду в цикле по строкам +столбцам, проверяю если элемент например a[i][j]!=0 иду дальше и считаю элементы, как только в строке встретил элемент = 0 выхожу из цикла,но что-то не улавливаю...

schwaВсе поле это один прямоугольник N на M. L - список, который содержит пригодные участки. Вначале он стоит из всего участка.
1) Берем первый непригодный участок. В соответствие с ним разбиваем (NxM) на нужно число частей. И добавляем полученные участки пригодные в L, удалив из него NxM.
2) Берем следующий непригодный участок. Находим какие он затрагивает участки из L и разбиваем их также как на шаге 1.
Дальше снова 2. До тех пор, пока не закончатся непригодные участки.

можете привести пример алгоритма, который вы написали?
интересует п.1 (В соответствие с ним разбиваем (NxM) на нужно число частей. И добавляем полученные участки пригодные в L, удалив из него NxM.)

визуально я понимаю как должно быть,спасибо.
а как например вычислить эти зоны?варианты между например 1,2,3 непригодными участками?если не трудно или на псевдо-коде или C,pascal

AndreTM,

тогда как быть?
я не совсем понимаю как получить варианты пригодных зданий?в контексте например той же матрицы?