시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 696 176 121 29.227%

문제

요즘 한창 잘 나가고 있는 XH 주식회사에서는 어린이용 장난감을 주력 사업으로 밀고 있다. 그 중 인기가 많은 제품은 역시 미로 탈출 게임인 째로탈출이다. 째로탈출은 다음 그림처럼, 미로 형태의 보드를 이용한 게임이다. 

째로탈출의 보드는 세로 N, 가로 M의 크기로 이뤄진 격자 형식으로 되어있다. 가장 바깥의 행과 열은 모두 막혀 있고, 가장자리에는 단 하나의 출구만 구멍이 뚫려 있다. 그림에는 없지만 째로탈출에는 구슬이 하나 들어있다. 게임의 목적은 구슬을 가장자리의 조그만 구멍을 통해 빼내는 것이다. 물론 째로탈출 보드에는 투명한 아크릴판이 덮여있어서 직접 빼내는 것은 불가능하고, 중력을 이용해 이리저리 굴리면서 빼내게 된다. 플레이어가 할 수 있는 동작은 다음과 같이 네 종류가 있다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기.

XH 주식회사에서는 째로탈출의 보드를 제작할 때, 비용 절감을 위해 공장에서 한 가지 모양으로만 찍어낸다. 하지만 장난감 가게로 배달하는 과정에서 흔들리기 때문에 제품을 받아보았을 때는 공의 위치는 빈 칸 어디에든 있을 수 있다.

이번 대회에서 우승한 kriii는 불투명한 포장지로 포장된 째로탈출을 상품으로 받았다. kriii는 공의 위치가 다 들여다보이는 째로탈출은 너무 쉬울 것이라고 생각했다. 그래서 '나는 포장 따윈 뜯어보지 않아도 이 퍼즐을 풀 수 있지!'라고 이야기하면서 모두의 앞에서 포장지를 뜯지 않고 째로탈출을 풀겠다고 선언했다. kriii가 이렇게 호언장담하며 선언한 이유가 있었다. 당신에게 몰래 이 보이지 않는 째로탈출의 풀이법을 알아내달라고 요청했기 때문이다! 당신은 kriii를 도와 공의 위치가 보이지 않는 째로탈출의 풀이법을 알아내야 한다.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

테스트 케이스의 첫 번째 줄에는 보드의 세로/가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양과 출구의 위치를 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 그리고 'O'만으로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 가장자리에 뚫린 출구의 위치를 의미한다.

입력되는 모든 보드의 가장자리에는 출구를 제외하고 모두 '#'이 있음이 보장된다. 빈 칸의 개수는 한 개 이상이다. 모든 빈 칸에서는 출구로 이어진 길이 있다는 것이 보장되어 있다. 이어진 길이라는 것은 공통된 변을 가진 빈 칸으로 이동할 수 있다는 것을 의미한다.

출력

각 테스트 케이스마다 한 줄을 출력한다. 빈 칸 어디에 공이 있든, 10회 이내에 항상 공을 빼낼 수 있는 방법이 존재한다면, 'L','R','U','D'로 이뤄진 문자열을 하나 출력한다. 각각 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기를 의미한다. 만약 10회 이내에 공을 뺄 수 있는 방법이 존재하지 않는다면 'XHAE'을 출력한다.

 

예제 입력

3
5 5
#####
#...O
#.#.#
#...#
#####
10 10
#O########
#...#.####
###.#....#
#...####.#
#.###....#
#...#.####
###.#....#
###..###.#
####.....#
##########
3 5
##O##
#...#
#####

예제 출력

LUR
XHAE
XHAE

힌트

  • 1번 케이스의 경우 UR은 불가능하다. 최초 공의 위치가 네 번째 줄 중앙에 있을 수도 있기 때문이다.
  • 2번 케이스의 경우 10번 이내로 빼낼 수 있는 방법은 존재하지 않는다.
  • 3번 케이스의 경우 어떤 방향으로 기울여도 빼낼 수 있는 방법은 존재하지 않는다.

출처

Contest > Coder's High > Coder's High 2014 E번