Кодовый замок

시간 제한2초메모리 제한1024 MB

요약
최대 30×30 격자에서 변을 공유해 연결된 k개 버튼 칸 부분집합의 개수를 센다. k는 10 이하이다.
난이도

어려움10점 중 8점

유형
DFS, 백트래킹, 구현, 조합론
정답자
아직 제출이 없습니다

문제

Компания <<Замки и замки>> недавно разработала новый тип кодового замка, для размещения на воротах замков. Панель замка представляет собой прямоугольник шириной ww ячеек и высотой hh ячеек. В некоторых из них расположены кнопки.

Код на этом замке вводится одновременным нажатием kk кнопок. Для того, чтобы код было легче запомнить, используемые в нем кнопки должны образовывать связную область. Область называется связной, если из любой клетки области можно добраться до любой другой, перемещаясь только между клетками этой области с общей стороной. Важным критерием надежности замка является число различных кодов, которые на нем можно набрать.

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

입력

В первой строке входного файла находятся три целых числа hh, ww и kk (1≤h,w≤301 \le h, w\le 30; 1≤k≤101 \le k \le 10). Каждая из последующих hh строк содержит ww символов. Символ <<#>> обозначает кнопку, а <<.>> --- ее отсутствие.

출력

В выходной файл выведите единственное число --- количество кодов, удовлетворяющих указанным требованиям.

힌트

На рисунке изображен один из возможных кодов для второго примера.

예제2

  1. 예제 1

    입력
    2 2 2
#.
##
    예상 출력
    2

  2. 예제 2

    입력
    5 6 7
.#....
##.##.
..#.#.
.####.
.....#
    예상 출력
    3