| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Компания <<Замки и замки>> недавно разработала новый тип кодового замка, для размещения на воротах замков. Панель замка представляет собой прямоугольник шириной $w$ ячеек и высотой $h$ ячеек. В некоторых из них расположены кнопки.
Код на этом замке вводится одновременным нажатием $k$ кнопок. Для того, чтобы код было легче запомнить, используемые в нем кнопки должны образовывать связную область. Область называется связной, если из любой клетки области можно добраться до любой другой, перемещаясь только между клетками этой области с общей стороной. Важным критерием надежности замка является число различных кодов, которые на нем можно набрать.
Для оценки надежности замков требуется написать программу для вычисления указанной величины.
В первой строке входного файла находятся три целых числа $h,ドル $w$ и $k$ (1ドル \le h, w\le 30$; 1ドル \le k \le 10$). Каждая из последующих $h$ строк содержит $w$ символов. Символ <<#>> обозначает кнопку, а <<.>> --- ее отсутствие.
В выходной файл выведите единственное число --- количество кодов, удовлетворяющих указанным требованиям.
2 2 2 #. ##
2
5 6 7 .#.... ##.##. ..#.#. .####. .....#
3
На рисунке изображен один из возможных кодов для второго примера.