题目描述

本题题解已发表至 讨论区

本题评测设置有误，评测结果仅供参考。

希罗打开了城市上空的巨大黑门，很多怪物穿过黑门来到了交界都市，快和尤梨一起拯救城市中的居民吧！

交界都市可以看作一个n行m列的网格，其中的一些区域有人需要救援。然而由于黑门怪物的影响，城市里有很多地方不能停留。幸运的是，尤梨拥有驯鹿雪橇，可以穿过黑门怪物群，到达区域里开展救援。但尤梨的行动是有规则约束的，尤梨只能横向或者竖向移动到相邻的没有黑门怪物的区域，不能斜向移动（相邻的定义为两个区域的x坐标或y坐标相等，且两个区域之间的线段上没有区域有人等待救援）；已到访的区域会在离开时被黑门怪物攻陷；抵达区域后的下一步移动方向不能与到访该区域的移动方向相同（不能走回头路）。

请你为尤梨规划一条从起点到终点并拯救了城市里所有人的路线

上图中，尤梨只能选择向上或向左走，到达如图所示的区域。

请输出你为尤梨规划的路线吧！如果路线存在，请输出一个由L，R，U，D组成的字符串（其中U代表向上走，D代表向下走，L代表向左走，R代表向右走），如果路线不存在，请输出-1。

注意终点必须最后到达。

可能存在多种不同的答案，请输出任意一种。大写与小写字母都会视作正确答案。

输入描述

第一行输入为n和m（1<=n,m<=8)，为网格大小

下面n行，每行m个字符，字符只可能是o，s，t，. 。

o代表有人的区域，.代表黑门怪物区，s代表起点，t代表终点。

数据保证有且仅有一个起点和一个终点。

输出描述

如果路线存在，请输出一个由L，R，U，D组成的字符串（其中U代表向上走，D代表向下走，L代表向左走，R代表向右走），如果路线不存在，请输出-1。

示例 1

输入

4 7
oooooo.
.....o.
...o..t
oo..oos

输出

LUULDLLURRRDR

示例 2

输入

4 7
o.os.o.
to..o.o
o.o.ooo
oo..oo.

输出

RDDLURULLDLURULD