헨젤과 그레텔 2초 128MB
문제
헨젤과 그레텔의 계모는 아이들을 숲속에 버리기로 계획했다. 그녀의 계획을 듣게된 헨젤과 그레텔은 집으로 가는 길을 표시하기 위해 하얀 조약돌을 A개 모았다.
계모가 아이들을 데리고 숲속 깊이 들어가는 동안 아이들을 하얀 조약돌을 하나씩 흘렸다. (헨젤과 그레텔은 같은 위치에 조약돌을 중복으로 흘리지 않는다.)
숲을 이차원 좌표평면으로 표현하자면 현재 헨젤과 그레텔의 위치는 (1,1) 좌표에 해당하고, 그들의 집은 (N,M) 좌표에 해당한다.
숲에는 바위나 나무 등으로 인해 이동이 불가능한 위치가 B개 존재한다. (불가능한 위치는 중복되지 않는다.)
아이들은 길을 잃지 않기 위해 오직 동쪽(X좌표가 증가함) 혹은 남쪽(Y좌표가 증가함)으로만 이동한다.
숲의 크기 세로 N과 가로 M와 하얀 조약돌의 위치를 의미하는 A개의 (X,Y)좌표와 이동을 방해하는 오브젝트의 위치를 의미하는 B개의 (X,Y)좌표가 주어졌을 때, 하얀 조약돌을 모두 회수하고 집에 돌아오는 경우의 수를 출력하시오.
입력
첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다.
A는 하얀 조약돌의 개수이고, B는 장애물의 개수이다.
다음 A개의 줄에는 하얀 조약돌의 위치, B개의 줄에는 장애물의 위치가 주어진다.
출력
첫째 줄에 경우의 수를 출력한다. 이때, 경우의 수가 21억 이하임이 보장된다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | 1 ≤ N, M ≤ 10 |
| #2 | 15점 | A == 1 |
| #3 | 70점 | 추가 제한 없음 |
예제
4 5 2 1
1 3
3 5
3 3
5
로그인해야 코드를 작성할 수 있어요.