코드 자물쇠

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

요약

30 by 30 격자에서 변을 공유하며 이어진 버튼 칸 k개로 이루어진 집합의 개수를 셉니다.

난이도: 보통10점 중 7점
유형: 비트 연산, BFS, 완전 탐색
정답자: 아직 제출이 없습니다

문제

회사 <<Замки и замки>>가 최근 문에 설치하는 새로운 종류의 코드 자물쇠를 개발했다. 자물쇠 패널은 가로 $w$ 칸, 세로 $h$ 칸으로 이루어진 직사각형이다. 일부 칸에는 버튼이 있다.

코드는 버튼 $k$ 개를 동시에 누르는 방식으로 입력한다. 코드를 외우기 쉽도록, 코드에 사용하는 버튼들은 연결된 영역을 이루어야 한다. 영역 안의 임의의 두 칸이 변을 공유하는 칸만 거쳐 서로 이동할 수 있으면 그 영역은 연결되어 있다. 이 자물쇠의 신뢰도를 판단하는 중요한 기준은 입력할 수 있는 서로 다른 코드의 개수다.

이 개수를 계산하는 프로그램을 작성하라.

입력

첫 줄에 정수 $h$ , $w$ , $k$ 가 주어진다 ( $1 \le h, w \le 30$ ; $1 \le k \le 10$ ). 이어지는 $h$ 줄에는 각각 $w$ 개의 문자가 주어진다. #은 버튼이 있는 칸, .은 버튼이 없는 칸을 뜻한다.

출력

조건을 만족하는 코드의 개수를 정수 하나로 출력한다.

힌트

그림은 두 번째 입력에 대해 가능한 코드 중 하나를 보여 준다.

예제2

예제 1
입력
```
2 2 2
#.
##
```
예상 출력
```
2
```

예제 2

입력

5 6 7
.#....
##.##.
..#.#.
.####.
.....#

예상 출력