SP13989 SUSY - Helping Susy

Susy 是一个既聪明又美丽的学生，她尤其擅长解决谜题游戏，尤其是迷宫游戏。这项才能让她在各种比赛中赢得了不少奖项，她的速度和技巧一直备受认可。 这次，她参加了一个特别的谜题比赛，而她的嫉妒对手 Angelica 也参与了。 目前，她们的分数打成平手。为了解决这个平局，裁判们设计了一场特别的比赛作为决胜局。游戏的规则是这样的： - 游戏由一个类似迷宫的表格构成，里面有墙壁。同时还有一些特殊道具——魔法石。想要赢得游戏，玩家必须收集齐表格中的所有魔法石。 - 玩家有四种可选的移动方向：上、下、左、右。一旦玩家选择了一个方向，就必须沿着这个方向移动，直到撞到墙壁才会停下来。显然，玩家不能超出表格的边界，因此表格边界也视作墙壁。 - 因为可能有多种解决方案，裁判们希望找出其中最优的一个，即使用最少移动次数的方案。 对于 Susy 来说，这并不是难题，但 Angelica 对此却感到无比头疼。出于嫉妒，Angelica 偷偷把 Susy 的解法撕成了许多碎片（她不是很聪明，其实可以直接复制，却因嫉妒而失去了理智）。 时间紧迫，Susy 再也没有时间重新解出谜题。不过幸运的是，参赛者允许请朋友帮忙解决一个谜题，而她知道你拥有评委们不知道的强大编程技能。 于是，她去求助你！编写一个程序以最少的移动次数解决这个迷宫，帮助 Susy 吧！

输入第一行是两个整数 $R$ 和 $C$，分别表示表格的行数和列数。 接下来的 $R$ 行每行有 $C$ 个字符，代表迷宫。迷宫中仅包含以下字符： - `.` - 空地， - `#` - 墙壁， - `S` - 玩家起始位置， - `*` - 魔法石。

输出一共两行。第一行只有一个数字 $S$，表示游戏的最优解所需的最少移动次数。 第二行由 $S$ 个字符串构成，用 `-` 分隔。这些字符串包括 "Up"、"Down"、"Left" 和 "Right"。这个字符串序列表示最优解中所有的具体移动。 如果有多个最优解，则输出字典序最小的一个方案。 **本翻译由 AI 自动生成**