JOI 2017 예선 3- 침대 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


3030 : 침대

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
45 회   
시도횟수
85 회   

문제

성빈이는 새로 이사를 가면서 자신의 방에 가구를 배치했다. 그러나 성빈이는 아직 침대를 배치하지 않았다. 성빈이는 침대를 어떻게 배치할지 견적을 보고 있다.

 

성빈이의 방은 가로 M, 세로 N 크기의 격자 모양으로 이루어졌으며 침대는 1 × D 크기이다. 침대는 90도 돌려서 배치할 수 있으며, 30도, 60도 등의 다른 각도로는 돌릴 수 없다. 또, 침대는 정확히 격자에 맞게 배치해야 하고 다른 가구나 벽이 있는 곳에는 침대를 놓을 수 없다. 아래 사진은 성빈이가 방에 침대를 배치할 수 있는 모든 경우를 나타낸다.

 


 

성빈이를 도와 방의 정보가 주어지면 침대를 놓는 방법의 수를 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 방의 크기 N, M과 침대의 길이 D가 주어진다. (1 ≦ N, M ≦ 100, 2 ≦ D ≦ 100)

두 번째 줄부터 N개의 줄에는 방의 정보가 주어진다. '.'는 빈 영역, '#'는 벽 혹은 가구가 놓인 곳을 의미한다.


출력형식

침대를 놓는 방법의 수를 출력한다.

입력 예

복사하기

3 5 2
...#.
#...#
....#

출력 예

복사하기

12

입력 예

복사하기

4 7 5
.#.....
.....##
.......
#......

출력 예

복사하기

7


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP