coci 2010/2011 contest6- 배관공(plumber) > 문제은행 : 정보올림피아드&알고리즘




2439 : 배관공(plumber)

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
8 회   
시도횟수
39 회   

문제

미치광이 배관공 마리오는 2개 도시 사이에 물을 공급하기 위한 네트워크를 건설하려고 한다. 도시의 지도는 R 행 S열의 격자형태로 표현된다. 지도상의 특정 칸은 파이프를 놓기 적합한 곳이 있다.

 


마리오는 맨왼쪽위의 위쪽 방향에서 부터 맨 오른쪽아래의 아래방향까지를 연결하여 물을 공급하려고한다. 파이프를 놓을 수 있는 칸에는 이를 그대로 두거나 다음과 같이 6개의 형태의 파이프를 놓을 수 있으며, 이를 회전하거나 뒤집어서 놓을 수는 없다. 굵게 표시된 선과 색칠된 부분이 파이프이며, 이 사이로 물이 흐르게 된다.


 



 


물이 흐르는 시작점과 끝점 사이에 물이 흐를 수 있게 파이프를 배치하는 경우의 수를 구하는 프로그램을 작성하라. 단, 놓여진 파이프 안에는 모두 물이 흘러야 한다. 상하좌우로 인접한 파이프 끼리는 맞닿아서 물이 흐를 수 있게 연결되어야 한다.

 


맨 위의 왼쪽 칸에는 3, 4번째 파이프를 사용할 수 있으며, 맨 아래쪽 오른쪽칸의 경우에는 4, 5번째 파이프를 사용할 수 있다.


입력형식

입력의 첫 줄에는 2이상 10이하의 숫자 R S가 입력된다. 그 다음 줄 부터 R개의 줄에는 지도에 표현된 도시의 각 칸을 뜻한다. '#'문자는 해당 위치에 파이프를 놓을 수 없음을 뜻하고 '.'의 경우에는 파이프를 놓을 수 있음을 뜻한다.


출력형식

입력에 대해 가능한 경우의 수를 10,007로 나눈 나머지로 출력한다.


입력 예

2 3
...
.#.

출력 예

1

Hint!

첫번째 예시는 다음과 같은 경우만 가능하다.

입력 예 2 3 3 ... ... ...

출력 예 2 12




경기도 안양시 동안구 평촌대로 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