격자 동물

시간 제한2초메모리 제한128 MB

요약

회전과 뒤집기를 같은 것으로 볼 때 w x h 직사각형 안에 들어가는 자유 n-폴리오미노의 개수를 센다. n은 10 이하이다.

난이도: 보통10점 중 7점
유형: 백트래킹, 완전 탐색, 기하, 해시맵
정답자: 아직 제출이 없습니다

문제

격자 동물(lattice animal) 은 격자 위에서 변으로 이어진 칸들의 집합이다. 정사각 격자 위의 격자 동물은 특히 널리 연구되며 폴리오미노(polyomino) 라고도 불린다. 폴리오미노는 보통 변끼리 맞닿아 연결된 단위 정사각형들의 집합으로 나타낸다. 정사각형이 $n$ 개인 폴리오미노를 $n$ -폴리오미노라고 한다.

이 문제에서는 $w \times h$ 직사각형 안에 들어가는 서로 다른 자유(free) $n$ -폴리오미노의 개수를 구해야 한다. 자유 폴리오미노는 회전하거나 뒤집을 수 있으므로, 회전한 모양과 거울상은 모두 같은 것으로 본다.

예를 들어 $2 \times 4$ 직사각형 안에 들어가는 펜토미노(5-폴리오미노)는 5가지이고, $3 \times 3$ 직사각형 안에 들어가는 옥토미노(8-폴리오미노)는 3가지이다.

입력

입력은 한 줄에 세 정수 $n$ , $w$ , $h$ 가 주어진다 ( $1 \le n \le 10$ , $1 \le w, h \le n$ ).

출력

$w \times h$ 직사각형 안에 들어가는 서로 다른 자유 $n$ -폴리오미노의 개수를 정수 하나로 출력한다.

예제5

예제 1
입력
```
5 1 4
```
예상 출력
```
0
```
예제 2
입력
```
5 2 4
```
예상 출력
```
5
```
예제 3
입력
```
5 3 4
```
예상 출력
```
11
```
예제 4
입력
```
5 5 5
```
예상 출력
```
12
```
예제 5
입력
```
8 3 3
```
예상 출력
```
3
```