게임 중독

면접 대비

시간 제한1초메모리 제한1024 MB

요약

홍수가 난 구역 y > x를 피해 두 대각선 점 사이를 잇는 최단 격자 경로의 수를 센다.

문제

강산이는 심각한 게임 중독자라서 날씨에 상관없이 매일 PC방을 간다.

최근 폭우로 일부 지역이 침수되어 침수된 지역으로는 이동할 수 없다. 그래도 강산이는 출석 이벤트를 위해 하루도 빠짐없이 PC방을 가야 한다.

강산이는 PC방까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동할 때의 거리는 1이다. 게임을 빨리하러 가야 하므로 강산이는 집에서 PC방까지 최단경로로 움직인다.

강산이의 집 좌표 $(H, H)$ 와 PC방 좌표 $(N, N)$ 이 주어지고, 좌표평면 위 $(x, y)$ 에서 $y > x$ 인 곳은 침수되었다고 할 때, 강산이가 침수된 지역을 피해서 PC방까지 갈 수 있는 경로의 개수를 구하라.

단, PC방의 좌표가 집의 좌표와 같은 경우 경로는 1가지라고 한다.

첫째 줄에 집과 PC방의 좌표 $(H, H)$ , $(N, N)$ 을 나타내는 두 정수 $H$ , $N$ ( $0 \le H, N \le 30$ )이 차례로 주어진다.

집에서 PC방까지 갈 수 있는 경로의 개수를 출력한다.