27895번 - 특별한 학생증 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 103 | 38 | 35 | 41.176% |
문제
NLCS Jeju 학생들은 교내에서 학생증(lanyard)을 착용해야 한다. 준석이는 학교의 통제 정책을 싫어하기 때문에 학생증을 착용하지 않고 다니는데, 선생님에게 걸리는 바람에 쫓기고 있다.
추격전을 벌이고 있는 준석이와 선생님을 목격한 교장 선생님은 학교를 미로로 바꾸었다. 미로는 가로 $N$, 세로 $M$의 2차원 격자로 표현될 수 있다. 좌상단에서 가로로 $x$칸, 세로로 $y$칸 떨어져 있는 칸은 $(x, y)$로 표현한다. 미로상의 각 칸은 비어 있거나, 포털이 설치되어 있거나, 벽으로 막혀 있다. $(0, 0)$와 $(N-1, M-1)$은 비어 있음이 보장된다.
각 포털은 다른 포털 하나와 연결되어 있다. 따라서 연결되어 있는 두 포털은 포털 쌍을 이룬다.
준석이는 다음 규칙에 따라 $(0,0)$에서 $(N-1, M-1)$으로 이동하려고 한다.
- 준석이가 뛰어서 이동하는 경우, $(x, y)$에서 $(x+1,y)$나 $(x,y+1)$로 이동할 수 있다. 단, 이동하고자 하는 칸이 벽으로 막혀 있으면 이동할 수 없다.
- 준석이가 포털이 설치된 칸에 있으면 포털을 이용하여 이동할 수 있다. 포털을 이용하는 경우, 연결된 포털로 순간 이동한다. 미로가 매우 급하게 만들어졌기에, 포털들은 매우 불안정하다. 따라서 하나의 포털을 사용하고 나면, 모든 포털이 고장나서 사용할 수 없는 상태가 된다.
준석이가 이동할 때 거치는 칸의 목록을 ‘경로’라고 정의하자. 가능한 경로의 가짓수를 세는 프로그램을 작성하시오.
입력
입력의 첫 줄에 $N$과 $M$, $K$가 공백으로 구분되어 주어진다. $N$과 $M$은 각각 미로의 가로·세로 칸 수를 나타낸다. $K$는 포털 쌍의 수를 나타낸다.
다음 $M$ 줄에 미로에 대한 정보가 주어진다. $M$개의 줄 중 $i$번째의 줄은 길이 $N$인 문자열로, $i$번째 줄의 $j$번째 문자는 $(j-1, i-1)$의 정보를 나타낸다.
0은 빈칸을 나타낸다. $(0, 0)$과 $(N-1,M-1)$은 빈칸임이 보장된다.1은 벽을 나타낸다.P는 포털을 나타낸다.
다음 $K$ 줄에 각 포털 쌍에 관한 정보가 주어진다. 각 줄에 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 공백으로 구분되어 주어지며, $(x_1, y_1)$과 $(x_2, y_2)$ 사이를 잇는 포털 쌍이 존재함을 의미한다. 각 포털의 좌표는 서로 다르며, 포털은 미로상에 P로 표시된 지점상에만 위치함이 보장된다.
출력
첫 번째 줄에 $(0, 0)$에서 $(N-1, M-1)$까지를 잇는 경로의 가짓수를 출력한다. 결과가 매우 클 수 있기 때문에, 결과를 $10^9+7$로 나눈 나머지를 출력한다.
제한
- $1 \leq N, M \leq 2\ 000$
- $0 \leq K \leq \min\left(\left\lfloor\frac{NM-2}{2}\right\rfloor, 500\ 000\right)$
예제 입력 1
3 3 1 0P0 P00 000 0 1 1 0
예제 출력 1
12
다음 12가지 경로를 통하여 이동할 수 있다.
예제 입력 2
4 3 3 0P0P P1P1 1PP0 0 1 1 2 2 1 2 2 1 0 3 0
예제 출력 2
4
다음 4가지 경로를 통하여 이동할 수 있다.
첫 번째 경로에서, 다음 그림과 같이 포털 C를 통하여 한 칸 아래로 이동하는 것과 포털을 사용하지 않고 이동하는 것은 방문하는 칸의 순서가 같으므로 같은 경로임에 유의한다.
힌트
나머지 연산에 대하여 다음이 성립한다.
- $(A + B) \bmod C = \{(A \bmod C) + (B \bmod C)\} \bmod C$
출처
High School > NLCS Jeju > GEC-Cup H번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호