Informatica Online Judge

  격전지 [2108 / 083C]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 21   Total Tried : 24


The Champion of this Problem (C++) : icp1481 - 0ms / 178byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16081]

Background

격전지에서 요원과 병사들이 잠복해 있다. 요원의 무전기가 울린다.
“요원, 지금 A 위치에서 대치 중인가?”
“그렇습니다, 오버.”
“지금 상황은 어떤가?”
“휴전선에 지뢰를 설치한 후 바로 B 위치, 본부로 복귀해야 하는데 적들이 우리의 움직임을 지켜보고 있어 곤란합니다.”
“그럼 어떻게 하는 것이 좋을까?”
“지금 지켜봤는데,
1) 왼쪽으로 가서는 안 되고, (적들이 병사의 위치를 포착하기 쉬워 사살당함)
2) 휴전선과 만나기 전에는 휴전선과 멀어지면(아래로 가면) 안 되고, (지뢰를 설치하지 않고 본부로 복귀하는 것은 국가에 대한 반역 행위로 간주, 요원이 직접 저격)
3) 휴전선과 만난 후 내려온 상태에서 B에 도착할 때까지 휴전선과 가까이 가면(위로 가면) 안 되고,
4) 휴전선과 두 번 이상 만나서는 안 되는 경로로만 가야 될 것 같습니다. (3, 4 모두 적국에 대한 도발로 간주, 적국이 그 병사의 위치를 치밀하게 포착하여 사살당함)”
“그 경로의 개수를 나에게 알려주게. 그럼 병사들의 손실을 줄이지 않게 경로의 수만큼 정확히 병사를 보내지. 병사들을 태운 헬기가 그쪽으로 갈 거야. 빠른 대답 바란다, 오버.”

요원을 도와, 대장이 A 위치에 파견을 낼 병사의 수는 몇 명인지 구하자.

위 그림은 격전지의 한 예로, 2*2 크기의 격자이다. 그림의 진한 선이 휴전선이다. 휴전선은 세로의 길이가 짝수라는 가정 하에, 위아래를 양분하는 선이다.
2*2 격자의 경우 직접 세어보면 6가지라는 것을 쉽게 알 수 있다.
참고로 "휴전선과 두 번 이상 만나서는 안 되는 경로"라는 것은 휴전선을 만난 후 내려왔다가 다시 휴전선을 만나지 못한다는 의미이다.

Input

첫 번째 줄에는 격전지의 가로, 세로를 나타내는 n, m이 주어진다. (단, m은 짝수, n, m<=16)

Output

첫 번째 줄에, A 위치에 파견을 낼 병사의 수를 출력한다.

IO Example

입력
2 2

출력
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]