시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
12 초 | 128 MB | 374 | 97 | 44 | 26.994% |
산타클로스는 노원구에 살고있는 모든 아이들에게 선물을 나누어 주려고 한다. 노원구에 있는 모든 집에는 아이가 있기 때문에, 산타클로스는 모든 집에 선물을 나누어 주어야 한다. 올해 산타가 타고 다닐 루돌프는 길치라서 건물 이외의 장소에는 내릴 수 없다. 따라서, 산타는 선물을 나누어줄 방법을 연구하려고 한다.
노원구는 1*1 크기의 영역으로 나누어져 있고, 각 영역은 집, 교회, 공터 중 하나이다. 노원구에는 교회가 하나 있다. 산타클로스와 루돌프는 교회에서 출발하여 모든 집에 선물을 나누어 주고, 다시 교회로 돌아가려고 한다. 또, 다음 규칙을 지켜야 한다.
도시의 구조가 주어졌을 때, 산타와 루돌프가 선물을 나누어주는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 마을의 가로 크기 m과 세로 크기 n이 주어진다. (1 ≤ m, n ≤ 10) 다음 n개 줄은 m개의 수가 공백으로 구분되어 주어진다. 각 수는 그 구역의 상태이며, 0, 1, 2중 하나이다. 0인 경우에는 공터, 집인 경우에는 1, 교회인 경우에는 2가 된다. 교회는 항상 1개이며, 집의 개수는 1개 이상, 23개 이하이다.
첫째 줄에 선물을 나누어 줄 수 있는 방법의 수를 출력한다. 이 값은 2000000보다 작거나 같다.
3 2 1 0 1 1 0 2
2
3 3 1 1 1 1 0 1 1 1 2
6