시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB257583821.111%

문제

가희는 거북이 인형을 좋아합니다. 거북이 등딱지에 위에 또아리를 틀고 앉으면 푹신하기 때문입니다.

 

[그림 1] 거북이 인형 위에서 또아리를 튼 가희

그런데 어느 날 거북이 인형이 엄마 주인 방으로 가 버렸습니다. 엄마 주인도 거북이 인형을 좋아하기 때문입니다.

엄마 주인을 제일 무서워 하는 가희는 엄마 주인이 자고 있을 때 몰래 거북이 인형을 리모컨으로 이동시켜서 자기 집에 놔두려고 합니다.

가희는 목적을 달성할 수 있을까요? 가희를 도와주세요.

입력

첫 줄에 맵의 세로 크기 R과 가로 크기 C가 주어집니다.

두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다.

문자열에 있는 문자는 가희의 집을 나타내는 'H', 거북이를 나타내는 'T', 장애물을 나타내는 '#', 빈 칸을 나타내는 '.' 중 하나입니다.

출력

가희가 어떤 순서대로 버튼을 눌러야 하는지 출력해 주세요. 버튼은 최소 횟수로 눌러야 하며, 거북이는 맵 바깥으로 이동할 수 없습니다.

또한 거북이를 이루는 'T'가 장애물이 있는 위치로 이동할 수 없습니다.

거북이 인형을 위로 1칸 이동하는 버튼은 U, 오른쪽으로 1칸 이동하는 버튼은 R, 아래로 1칸 이동하는 버튼은 D, 왼쪽으로 1칸 이동하는 버튼은 L입니다.

만약에, 거북이 인형이 가희 집으로 갈 수 없다면 -1을 출력해 주세요.

거북이 인형이 가희 집에 갔다는 의미는, 거북이 인형 중 일부분이 가희 집의 위치에 있다는 것을 의미합니다.

제한

  • 2 ≤ R ≤ 1000
  • 2 ≤ C ≤ 1000
  • 거북이 인형은 맵 안에 하나만 있으며, 거북이 인형을 나타내는 'T'들이 상하좌우로 인접한 형태로 주어집니다.
  • 가희 집을 나타내는 'H'는 하나만 주어집니다.
  • 장애물을 나타내는 '#'는 많아봐야 20번 등장합니다.

예제 입력 1

5 5
.....
.TTT.
..HT.
.TTT.
.....

예제 출력 1

U

가희는 리모콘의 버튼을 1번 눌러서, 거북이 인형의 일부분을 자기 집에 놓을 수 있습니다.

 

  
[그림 2] 거북이 인형의 처음 위치와 (왼쪽) 가희가 리모컨의 U 버튼을 한 번 눌렀을 때 (오른쪽)

 

이 방법 말고도, D 버튼을 한 번 누르거나, L 버튼을 한 번 눌러도 됩니다.

R 버튼을 누르고 L 버튼을 누른 다음에 L 버튼을 눌러도 되지만, 이 경우는 최소 횟수로 누른 것이 아니므로 답이 되지 않습니다.

예제 입력 2

10 10
..........
...TTT....
.....T....
....TT....
...HT.....
..........
..........
..........
..........
..........

예제 출력 2

L

거북이 인형이 왼쪽으로 한 칸 가면, 거북이 인형의 일부분이 가희 집이 있는 위치로 가게 됩니다.

예제 입력 3

10 10
..........
...TTT....
.....T....
....TT....
..H#T.....
..........
..........
..........
..........
..........

예제 출력 3

ULLD

거북이는 왼쪽 방향으로 갈 수 없습니다. 거북이 왼쪽 바로 옆에 장애물이 있기 때문입니다.