1 Отредактировано Ramazan (2012-03-02 14:10:08)

Тема: помогите решить ету задачу

Администрация города Байттауна решила построить конькобежную трассу в центральном парке, который представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м2. Другими словами парку соответствует прямоугольная таблица с N строками и M столбцами.  Строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы. Следовательно, каждому квадрату можно поставить в соответствие пару числа (X, Y), где
X – это номер строки, а Y – номер столбца, на пересечении которых  он находится.
Все квадраты парка делятся на два типа: содержащие дерево либо не содержащие дерево (пустой квадрат).  Будем считать, что если квадрат содержит дерево, то  оно занимает всю его площадь.

Длиной трассы будем считать количество квадратов, через которые проходит трасса. Конькобежная трасса должна иметь квадратную форму, причем её длина должна быть не меньше L метров, а ширина – ровно один метр. Границы трассы должны быть параллельны границам парка и проходить по линиям, которые разделяют его на квадраты. Трасса не может проходить через квадраты, которые содержат деревья. На рисунке выше приведен пример трех возможных размещений трассы.
Вам даны числа N, M, L, описание всех квадратов парка, то есть для каждого из квадратов известно, пустой он или нет. Вам требуется по заданным исходным данным определить количество различных способов построения конькобежной трассы. Способы считаются различными, если им соответствуют различные множества квадратов.


n <= 1000
m <= 1000
l <= 10^9

2

Re: помогите решить ету задачу

Простой перебор.

3 Отредактировано Ramazan (2012-03-02 14:11:41)

Re: помогите решить ету задачу

izvinite,  ograni4inie ne pozvolyut

4

Re: помогите решить ету задачу

Это же белорусская респа 2011, если я правильно понял.
Тогда сначала посчитаем для каждой клетки ДП:
r[ i ][j] - ближайшее справа дерево, l[ i ][j] - ближайшее слева дерево, u[ i ][j] - ближайшее сверху дерево, d[ i ][j] - ближайшее снизу дерево. Теперь f[ i ][j]=min(u[ i ][j],l[ i ][j]) - (неформально) насколько ячейка может быть правой нижней у квадрата, g[ i ][j]=min(r[ i ][j],d[ i ][j]) - насколько ячейка может быть левой верхней у квадрата. Посчитали все это за O(N^2) и теперь смотрим нашу матрицу подиагонально, ставим и убираем единички в сумматоре с учетом f и g, и получаем решение за O(N^2*logN). http://pastebin.com/8mbbMtEH - мой код, правда он очень старый и малочитаемый.