프로그램 명: coci_voda
제한시간: 5 초
파이프를 연결하는 일을 하는 배관공 미르코는 두 도시의 수도관망을 연결하기 위해 고용되었다. 도시의 맵은 R × S 격자 형태로 표현이 가능하다. 몇몇의 셀들은 파이프를 놓는데 적절하지 않다. 미르코가 연결해야 할 장소들은, 왼쪽 위 셀과 오른쪽 아래 셀에 위치해있다.
미르코가 사용할 수 있는 파이프는 다음과 같이 6종류가 있다.
두 장소를 파이프를 계속 이어서 연결할 수 있는 경우의 수를 찾아라. (물은 파이프 밖으로 흐르지 않는다.) 모든 장소에 있는 파이프는 사용되어야 한다.
정답은 10007로 나누어준다.
입력
격자의 크기를 의미하는 R,S가 첫줄에 입력되고 (2 ≤ R, S ≤ 10), 파이프를 놓을 수 있는 공간인 '.'과 놓을 수 없는 공간인 '#'이 R × S 사이즈로 입력된다. 자세한 것은 입력을 참고한다.
출력
모든 경우를 10007로 나눈 나머지를 출력한다.
Mirko, the mad plumber, was hired to construct a water supply network between two locations in a city. The city map can be represented as a R × S grid. Some cells are not suitable for placing water pipes. Locations Mirko needs to connect are placed directly above the top left cell of the grid, and directly below the bottom right cell.
Each suitable cell Mirko can either leave empty or use it for placing one of the following 6 pipe types:
Find the number of ways that pipes can be placed to connect the two locations with a continuous pipe (water must not be spilled). All placed pipe parts must be in use.
Output the solution modulo 10007.
입력
The first line of input contains the integers R and S (2 ≤ R, S ≤ 10), the number of rows and columns of the city grid, respectively. Each of the next R lines contains exactly S characters: ‘.’ if the cell is suitable for placing pipes, and ‘#’ if not.
출력
The first and only line of output must contain the required number of ways modulo 10007..
입출력 예
input
2 3
...
.#.
output
1
input
3 3
...
...
...
output
12
First sample description: this is the only possible solution:
출처:coci
번역:pl0892029
[질/답]
[제출 현황]
[푼 후(0)]