17145번 - 청소 로봇 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 103 | 26 | 18 | 26.866% |
문제
당신의 물류 창고가 너무 지저분해서 청소를 하려고 청소 로봇을 구입했다. 물류 창고는 테이블 (그리드) 모양이며 총 R행 C열로 구성되어있다. 각 행 각 열에는 엄청나게 거대한 물류 선반이 있으며 사람이 청소할 수 없을 만큼 방대하다. 아래 예는 4행 6열로 구성된 물류창고를 나타낸다.
당신은 상/하/좌/우로만 이동 할 수 있는 청소 로봇을 r행 c열에 배치하고, 이 로봇이 모든 선반을 딱 한 번씩만 방문하여 청소할 수 있는지 알고 싶다.
예를 들어 R = 4, C = 6, r = 3, c = 2인 경우 로봇을 3행 2열 (위에서 세 번째 좌에서 두 번째)에 배치한 경우 로봇이 아래 그림과 같은 순서로 1~24번째 칸을 방문하며 모든 선반을 한 번씩 청소할 수 있다. 이 로봇의 이동 경로는 상(U)하(D)좌(L)우(R) 표현 방식을 통해 길이가 23일 문자열로도 표현 가능하다: “URDDRRRULLURRULLLLLDDDR”.
어떤 경우에는 로봇이 모든 칸을 정확히 한 번씩 방문하는 것이 불가능 할 수 있다. 가령 R = 3, C = 3, r = 1, c = 2 인 경우, 모든 칸을 정확히 한 번씩만 방문할 수 있는 방법이 존재하지 않는다.
R, C, r, c가 주어졌을 때 청소 로봇이 모든 칸을 딱 한 번씩만 방문하여 선반을 청소하는 것이 가능한지 결정하는 프로그램을 작성하시오. 만약 가능하다면 로봇이 어떻게 움직여야 하는지 상/하/좌/우 표현 방식을 이용하여 출력하시오. 로봇은 상/하/좌/우로만 이동 가능하며 물류창고 밖으로 나갈 수 없다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 <= T <= 100).
각 테스트 케이스는 한 줄에 주어지며 R, C, r, c 네 개의 정수가 공백으로 구분되어 주어진다.
모든 테스트 케이스는 다음을 만족한다: 1 <= R, C <= 100 그리고 1 <= r <= R 그리고 1 <= c <= C. 마지막으로, R*C는 항상 1을 초과하는 값이다 (물류창고에는 언제나 선반이 하나 보다 많다).
출력
각 테스트 케이스에 대해 한 줄에 문자열 하나를 출력해야 한다.
만약 모든 칸을 딱 한 번씩 방문하는 것이 불가능 하면 “IMPOSSIBLE” (따옴표 제외)을 출력한다.
가능한 경우, 길이가 (R*C)-1인 문자열을 이용하여 로봇의 이동 경로를 상(U)/하(D)/좌(L)/우(R)을 이용하여 출력한다. 상하좌우 순서대로 로봇이 위로 (행의 번호가 낮아짐), 아래로 (행의 번호가 높아짐), 왼쪽으로 (열의 번호가 낮아짐), 오른쪽으로 (열의 번호가 높아짐) 움직이는 것을 나타낸다.
서브태스크 1 (10점)
- 1 <= R, C <= 5
서브태스크 2 (21점)
- 1 <= R, C <= 100
예제 입력 1
6 2 2 1 1 3 3 1 2 3 3 2 2 5 5 3 2 4 6 3 2 1 3 1 2
예제 출력 1
RDL IMPOSSIBLE LURRDDLL IMPOSSIBLE RDLLUURRRDDRRULURULLLLL IMPOSSIBLE
힌트
첫 예제의 경우 “DRU” 도 정답이다.
두 번째 예제의 경우 모든 칸을 정확히 한 번씩 방문하는 것은 불가능하다.
세 번째 예제의 경우 정답이 여럿 존재하는데 그 중 무엇을 출력해도 무방하다.
네 번째 예제는 불가능하다.
다섯 번째 예제는 정답이 여럿 존재하며, 다른 정답이 문제에서 예시로 언급되었다.
마지막 예제는 불가능하다.
문제의 정답이 여러가지인 경우에는 스페셜 저지로 채점을 하게 됩니다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식입니다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호