| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 30 | 23 | 23 | 82.143% |
큰일이다. 아침 수업인데 늦잠을 자버렸다.
바깥엔 비바람이 휘몰아친다.
우산을 폈다. 뒤집혔다. 하늘로 솟구쳤다.
멀어지는 우산이 나를 부르는 것만 같다.
그래! 수업에 늦지 않을 방법은 단 하나뿐!
자취방을 나선 윤이는 바람에 몸을 맡기고 학교까지 날아가기로 결심했다. 하지만 오늘의 태풍은 만만치 않을 것이다.
윤이가 사는 동네의 지도는 $H\times W$ 격자로 나타낼 수 있다. 각 격자칸은 빈칸이거나 건물이다. 일기 예보에 따르면 태풍은 매초 주어진 방향에 따라 총 $T$초 동안 몰아치며, 그 뒤에는 잠잠해진다.
윤이는 매초 바람의 방향을 따라 한 칸 날아간다. 바람 방향의 반대편에 건물이 있다면, 날아가는 대신 건물 벽을 붙잡고 그 자리에서 버티는 선택도 가능하다. 하지만 윤이가 날아가는 방향에 건물이 있다면 강력한 운동 에너지를 경험하고 기절할 것이다. 또한 윤이가 지도 밖을 벗어난다면 태풍에 삼켜지고 말 것이다.
윤이는 $T$초 동안 다치지 않고 날아다니다가, 태풍이 잠잠해지는 순간 강의실 건물 앞에 정확히 안착할 계획을 세웠다. 윤이의 계획은 과연 성공할 수 있을까?
첫째 줄에 격자의 크기를 나타내는 정수 $H$, $W$가 공백으로 구분되어 주어진다. $(1\le H,W\le 1\, 000)$
둘째 줄에 윤이가 출발한 위치의 좌표 $(r_s,c_s)$가 공백으로 구분되어 주어진다. $(1\le r_s\le H;1\le c_s\le W)$
셋째 줄에 윤이가 도착할 위치의 좌표 $(r_e,c_e)$가 공백으로 구분되어 주어진다. $(1\le r_e\le H;1\le c_e\le W)$
다음 $H$개의 줄에 격자를 나타내는 길이 $W$의 문자열이 주어진다. 각 문자의 의미는 다음과 같다.
.: 빈칸#: 건물다음 줄에 $T$초 동안 바람이 부는 방향을 나타내는 길이 $T$의 문자열이 주어진다. $(1\le T\le 10^6)$ 각 문자의 의미는 다음과 같다.
U: 위 방향으로 부는 바람R: 오른쪽 방향으로 부는 바람D: 아래 방향으로 부는 바람L: 왼쪽 방향으로 부는 바람모든 좌표는 행, 열 순서로 주어지며, 가장 왼쪽 위 좌표는 $(1,1)$이다. 윤이가 출발한 위치와 도착할 위치에는 건물이 없음이 보장된다.
윤이가 정확히 $T$초 뒤에 목적지에 도착할 수 있으면 첫째 줄에 YES, 그렇지 않으면 NO를 출력한다.
YES를 출력한 경우, 둘째 줄에 윤이의 계획을 나타내는 길이 $T$의 문자열을 출력한다. 각 문자의 의미는 다음과 같다.
F: 바람을 타고 한 칸 날아간다.G: 바람 방향의 반대편에 있는 건물을 붙잡고 그 자리에 있는다.가능한 답이 여러 가지라면 그중 아무거나 하나를 출력한다.
4 5 3 4 2 2 ...## ...#. #.... ##... LLUUURLL
YES FFGGFFGF
3 3 2 2 2 2 ... ... .#. UUUUUD
YES GGGGFF
3 3 2 2 2 2 ... ... .#. UUUUUDD
NO
4 4 3 3 3 3 .... .... .... .... LLUURRDDD
NO
University > UNIST-DGIST-POSTECH > 2026 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2026 UDPC) > Junior Division F번