TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

98.3% (57/58)

Submission's AC Ratio

61.5% (64/104)

Tags

Description

現在是中午的練習時間,可是seanwu在打Ballance。這種遊戲是這樣的,畫面中間有一顆球,你可以使用方向鍵來讓它移動,目標是解開重重的關卡,讓球滾到目的地。

可是,這次seanwu在一個該死的迷宮卡關卡了很久,於是他決定改良這個遊戲,使玩家可以不用把這麼多時間浪費在這個遊戲上面。
新版的Ballance,長得像底下這樣:

S是球的起點,T是要前往的目的地,且為了不讓遊戲者花太多時間在這個遊戲上面,因此從起點到終點的路線上,完全沒有岔路,這樣你就可以快速的直達目的地,不用花時間走迷宮、解謎。
現在給你遊戲的地圖,你必需讓球從起點S滾到終點T,你可以讓球向上、下、左、右等方向移動,分別以U、D、L、R來表示。請你找出完成任務的移動方法。
注意,每個空格上都設有陷阱,只要同一個格子走超過一次,就會爆炸。

Input Format

輸入的第一行有一個正整數,代表接下來會有幾組測資(不超過10組),每組測資之間以空白行分隔。

接下來的每組測資中,第一行有兩個正整數N,M(0<N,M<20),分別代表地圖的高和寬,

接下來會有N行,每行M個字元表示這個地圖,'.'為空格,'#'為牆壁,S為起點,T為終點。

Output Format

對每一組測資,輸出正確的移動方式。

Sample Input 1

3

5 6
######
#S..##
###.##
###.T#
######

4 5
#####
#S#T#
#.#.#
#...#

11 17
##..###..#######.
####...#.......#.
.#S#.#..######...
##.#..#.......#.#
##..#.#######.#..
..#...###.###.##.
######....#T..#..
.#...#.#..#####.#
.#.#.##.#........
.###.###########.
.###.##..........

Sample Output 1

RRDDR
DDRRUU
DDRDRRUULUURRDRDRRRRRRDDDLL

Hints

Problem Source

原TIOJ1183 / TFcis 10th留社考(prob E)。Problem Setter:seanwu。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1