| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 137 | 50 | 35 | 32.110% |
Albert와 Bob은 "과자 줍기" 보드 게임을 즐겨한다.
이 게임은 크기가 $R \times C$ 인 격자 보드를 사용하여 진행하는데, 먼저 Bob이 $N$개의 칸을 골라 과자를 올려둔다. 단, 각 칸에는 최대 1개의 과자만 올려둘 수 있고 좌측상단 $(1, 1)$ 혹은 우측하단 $(R, C)$에는 과자를 올려둘 수 없다. 이후 Albert는 게임 말을 $(1, 1)$칸에 올려둔 후 우측 혹은 아래로만 이동하여 $(R, C)$ 칸에 도달하여야 하고 이동한 경로를 따라 최대한 많은 과자를 주워야 한다. 예를 들어 아래 그림의 경우 $R = 3, C = 5$ 그리고 $N = 3$인 경우를 나타낸다. 편의상 과자의 위치는 크기가 $N$인 두 배열 $X, Y$로 행/열을 나타내기로 하며 아래 예제의 경우 $X = [1, 1, 2]$ 그리고 $Y = [3, 4, 3]$이 된다.
S로 표시된 $(1, 1)$ 에서 출발하여 E로 표시된 $(3, 5)$ 칸으로 가는 방법은 여럿 존재하는데, 아래 그림과 같은 방법으로 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 5)$ 로 이동한다면 1개의 과자만 줍게 된다.
하지만 아래와 같이 여섯 가지 다른 방법으로 총 2개의 과자를 주울 수도 있다.
이 예제에서 과자를 3개 주우면서 S칸에서 E칸으로 도달하는 방법은 없다.
Albert는 입력으로 주어진 보드에서 최대한 많은 과자를 줍는 서로 다른 방법의 수가 몇 가지나 되는지 궁금해졌다 - Albert를 도와 이 값을 구해보자. 위 예제의 정답은 6이다.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $R, C, N$ 값이 공백으로 구분되어 주어진다. 다음 $N$줄에 걸쳐 각 줄에 $i$번째 과자가 놓인 칸의 행 위치 ($X_i$)와 열 위치 ($Y_i)$ 가 공백으로 구분되어 주어진다.
각 테스트 케이스에서 시작 칸 $(1, 1)$에서 도착 칸 $(R, C)$까지 이동하며 최대한 많은 과자를 줍는 방법의 수를 각 줄에 출력한다. 단, 이 수가 매우 클 수 있으므로 1000003으로 나눈 나머지를 출력한다.
4 3 5 3 1 3 1 4 2 3 3 5 2 2 2 3 3 4 4 1 1 4 4 4 2 4 1 2 4
6 4 1 5
예제 1: 본문에서 다루었다.
예제 2: 아래와 같은 4가지 방법이 존재한다.
예제 3-4: 추가 설명 없음.