|
2010-2011
|
Беговая дорожка (100 баллов)
Байт-таун является столицей Байтландии. Это очень красивый и богатый город в центре страны. Архитектура и природа поражает воображение. Каждый год количество туристов, приезжающих погостить в этот чудный год, неуклонно увеличивается. Центральный парк является главной достопримечательностью Байт-тауна. Парк представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м2. Таким образом, парк – это прямоугольная таблица с N строками и M столбцами. Строки нумеруются сверху вниз начиная с единицы, столбцы нумеруются слева направо начиная с единицы. Следовательно, каждой ячейке (квадрату) можно поставить в соответствие уникальную пару числа (X, Y), где X – это номер строки, а Y – номер столбца, на пересечении которых находится данный квадрат. Все квадраты парка делятся на два типа: содержащие дерево, и не содержащие дерево (свободный квадрат). Будем считать, что если квадрат содержит дерево, то дерево, находящееся в данном квадрате, занимает всю его площадь.
Рисунок №1. Описание второго примера.
В целях оздоровления нации администрация Байт-тауна решила построить в парке беговую дорожку прямоугольной формы длинной S метров и шириной один метр. Дорожка должна вписываться в структуру парка, то есть границы дорожки должны быть параллельны границам парка и проходить по границам парка, которые разделяют его на квадраты. Однако экологи Байтландии строго-настрого запретили вырубку деревьев, что существенно ограничивает свободу выбора размещения дорожки, так как дорожка может проходить только через свободные квадраты. На рисунке выше приведен пример двух из 11 возможных размещений беговой дорожки. Вам даны числа N, M, S, описание всех квадратов парка, то есть для каждого из квадратов известно, свободен он или нет. Вам требуется по заданным исходным данным определить количество различных способов построения беговой дорожки. Способы считаются различными, если им соответствуют различные множества ячеек. Входные данные Первая строка входного файла содержит ровно три целых числа, разделенных одиночными пробелами – это числа N, M, S (2 ≤ N, M, S ≤ 250).
Следующие
N строк содержат строковые величины, состоящие из M символов, которые описывают
парк, j-й символ в i-й по счету строковой величине описывает тип квадрата.
Символ ‘.’(ASCII 46) – квадрат с координатами (i, j) является свободным, символ
Выходные данные Выходной файл должен содержать одно целое число – количество различных способов построения беговой дорожки.
|
