题目描述

本题难度较高，同学们不一定要完成，感兴趣可以了解一下BFS，DFS，A*等路径算法

智能视觉小车需要在一个 8×8 的方格地图中，将唯一的箱子推到指定目标点。

地图由以下字符组成：

• #：墙壁，小车和箱子均不能进入；
• -：空地；
• S：小车的起点；
• B：箱子的初始位置；
• D：箱子的目标点。

小车每次只能向上、下、左、右移动一格。若小车移动方向上的相邻格是箱子，则小车会尝试推动箱子向同一方向移动一格；只有箱子前方的格子在地图内且不是墙壁时，这次推动才合法。小车不能拉动箱子。

请输出把箱子推到目标点所需的最短完整移动路线。路线既包含小车普通行走（包括绕到箱子另一侧的动作），也包含推动箱子的动作。

若最短路线不唯一，则按本题规定的字符优先级 U < D < L < R，输出字典序最小的路线。

本题源自今年第21届全国大学生智能汽车竞赛"人工智能视觉"组别，该赛题需要小车在12*16大小的地图中即时规划最短路径，推进3~5个箱子，还需识别对应和使用炸弹开墙。

输入格式

输入共 8 行，每行包含一个长度为 8 的字符串，表示地图。

输入保证：

• 地图中恰好有一个 S、一个 B 和一个 D；
• 其余字符只可能是 # 或 -；
• S、B 和 D 位于不同格子。

输出格式

若箱子无法到达目标点，输出一行：

IMPOSSIBLE

若存在可行路线，输出两行：

• 第一行输出最少移动次数；
• 第二行输出对应的完整路线字符串。

路线字符含义：

• U：小车向上移动；
• D：小车向下移动；
• L：小车向左移动；
• R：小车向右移动。

推动箱子也只记作小车本次移动方向对应的一个字符。

判定规则

使用标准输出比较。答案必须同时满足：

1. 路线合法，且最终箱子位于 D；
2. 小车移动总次数最少，普通行走和推动箱子均计为一次移动；
3. 多条最短路线中，按 U < D < L < R 比较时字典序最小。

比较两条路线时，从左到右找到第一个不同字符，并按照上述自定义优先级确定大小。

样例

########
#S-----#
#-###--#
#--B---#
#-##---#
#----D-#
#------#
########

13
DDRRRDRRUULDD

样例说明

小车先移动到箱子左侧，将箱子向右推动两格；随后绕到箱子上方，再将箱子向下推动两格到达目标点。

输出路线中的 DRRUUL 是小车绕到箱子上方所经过的普通行走动作，也必须计入答案。整条路线共移动 13 次。

数据范围与限制

• 地图大小固定为 8×8；
• 机器人和箱子均不能越过地图边界或进入墙壁；
• 时间限制：1 秒；
• 空间限制：64 MiB。