Evro78
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
До чемпіонату Європи з футболу адміністрація одного з міст України вирішила збудувати бігову доріжку у центральному парку міста, який представляє собою прямокутник розміром N на M метрів, розділений на квадрати площею 1 м2. Іншими словами парку відповідає прямокутна таблиця з N рядками і M стовпчиками. Рядки нумеруються зверху вниз, починаючи з одиниці, стовпчики – зліва направо, починаючи з одиниці. Отже, кожному квадрату можна поставити у відповідність пару чисел (X, Y), де X – це номер рядка, Y – номер стовпчика, на перетині яких він знаходиться. Усі квадрати парку поділяються на два типи: ті що містять дерево або ті, що не містять дерево (порожній квадрат). Будемо вважати, що якщо квадрат містить дерево, то воно займає всю його площу
Малюнок №1. Опис першого прикладу 3 варіанта: довжиною 8м, 8м і 12м відповідно.
Довжиною доріжки будемо вважати кількість квадратів, через які вона проходить. Бігова доріжка повинна мати квадратну форму, і до того ж її довжина має бути не менша L метрів, а ширина – рівно один метр. Межі доріжки мають бути паралельними межам парку і проходити по лініях, які розділяють його на квадрати. Доріжка не може проходити через квадрати, що містять дерева. На малюнку вище наведено приклад трьох можливих розміщень доріжки. Вам дані числа N, M, L, описи усіх квадратів парка, тобто для кожного із квадратів відомо, порожній він чи ні. Вам потрібно визначити кількість різних способів побудови бігової доріжки. Способи вважаються різними, якщо їм відповідають різні множини квадратів.
Вхідні дані
перший рядок вхідного файлу містить три цілих числа, розділених одиночними пробілами N, M (2 ≤ N, M ≤ 1000) і L(2 ≤ L ≤ 109) відповідно. Наступні N рядків містять по M символів, які описують парк, j-ий символ у i-ому рядку описує тип квадрата. Символ «.» (ASCII 46) – квадрат з координатами (i, j) є порожнім, символ «#»– квадрат з координатами (i, j) містить дерево.
Вихідні дані
єдиний рядок вихідного файлу має містити одне число – кількість різних способів побудови бігової доріжки.
Ввод
5 6 8
.#....
.....#
......
.#..#.
.....#
Вівод
3 |
