문제
세계적인 프로그래밍 대회가 일본에서 열리게 되어, 지금 경기장을 꾸미고 있다. 경기장은 남북으로 \(N\)칸, 동서로 \(M\)칸의 격자이고, 몇몇 칸에는 경기용 장비가 놓여 있다. 이 대회에서는 선수가 경기 중에 쉴 수 있도록, 간단한 음식과 음료를 두는 휴식 공간을 경기장 안에 \(1\)곳 만들기로 했다. 휴식 공간은 남북 또는 동서로 이어진 \(D\)칸이어야 한다. 장비가 놓인 칸에는 휴식 공간을 둘 수 없다. 경기장 안에 휴식 공간을 두는 방법이 몇 가지인지 구하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(M\) \(D\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_N\)
- 입력은 \(1+N\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\), \(D\)가 공백 하나로 구분되어 주어진다. 경기장이 남북으로 \(N\)칸, 동서로 \(M\)칸의 격자이고, 휴식 공간이 남북 또는 동서로 이어진 \(D\)칸임을 나타낸다.
- 이어지는 \(N\)줄에 각각 길이 \(M\)의 문자열이 공백 없이 주어지고, 경기장 정보를 나타낸다. \(i\)번째 줄의 \(j\)번째 문자(\(1 \le i \le N\), \(1 \le j \le M\))는 북에서 \(i\)행, 서에서 \(j\)열 칸의 상태이고 # 또는 . 이다. # 은 그 칸에 장비가 있음을, . 는 장비가 없음을 나타낸다.
- \(1 \le N \le 100\)
- \(1 \le M \le 100\)
- \(2 \le D \le 100\)
출력
다음 형식으로 출력한다.
첫째 줄에, 경기장 안에 휴식 공간을 두는 방법의 수를 출력한다.
예시 1
입력
3 5 2
...#.
#...#
....#
출력
12
설명
장비가 없는 칸이 남북 또는 동서로 \(2\)칸 이어진 자리를 고르는 방법은 모두 \(12\)가지이다.
예시 2
입력
4 7 5
.#.....
.....##
.......
#......
출력
7