시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 27 | 3 | 3 | 100.000% |
민제는 미로 게임장을 운영하고 있다. 게임장에 있는 미로는 N행 M열 크기의 격자 모양이고, 각 칸에는 상, 하, 좌, 우 네 방향 중 하나가 쓰여 있다. 미로 안을 돌아다닐 때는 네 방향으로 이동할 수 있으나, 자신이 위치한 칸에 적혀 있는 방향이나 미로를 벗어나는 방향으로는 이동할 수 없다.
민제는 미로에 참가자가 한 번 들어갔다 나올 때마다 미로를 청소하는데, 매번 N × M개의 칸을 모두 청소하다가 골병이 들고 말았다. 민제는 참가자가 돌아다니지 않은 칸은 굳이 청소할 필요가 없다는 걸 깨닫고, 앞으로는 참가자가 지나갔을 가능성이 있는 칸만 청소하기로 했다.
각 참가자가 미로 탐험을 시작한 위치와 끝낸 위치가 주어질 때, 민제가 청소해야 할 칸의 수를 구하는 프로그램을 작성하여라.
첫 번째 줄에는 미로의 크기 N, M (1 ≤ N, M ≤ 1,000), 쿼리의 수 Q (1 ≤ Q ≤ 300,000)가 주어진다.
두 번째 줄에는 N개의 줄에는 미로의 형태에 해당하는 M개의 문자가 주어진다. 각 문자는 U
, D
, L
, R
중 하나이며 이는 미로의 해당 칸에서 각각 위, 아래, 왼쪽, 오른쪽으로 이동할 수 없음을 의미한다.
N+2번째 줄부터 Q개의 줄에는 시작점의 행 번호와 열 번호, 도착점의 행 번호와 열 번호가 주어진다. 시작점과 도착점이 같을 수 있으며 참가자가 도착점에 처음 도달한 다음에도 미로 탐험을 계속할 수 있음에 유의하여라.
Q개의 줄에 걸쳐 각 줄에 쿼리에 대한 정답을 출력하는데, 시작점에서 도착점까지 이동할 수 없으면 0
을 출력하고 그렇지 않으면 민제가 청소해야 할 칸의 수를 출력한다.
5 5 5 DDDDD RDDDL RRDLL RUUUL UUUUU 1 1 5 5 2 2 5 5 3 3 5 5 4 4 5 5 5 5 5 5
0 14 20 14 5
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2019 I번
Contest > Open Cup > 2019/2020 Season > Stage 5: Grand Prix of Korea C번