希蒙生成随机迷宫最短路

题目描述

希蒙有一个机器人在移动，要从某个点到另一个点，给定其在某一迷宫（不给出该迷宫）移动的序列，序列中只包含大写字母UDLR，问这条路径是否可能是最短的路径（您可以在迷宫任意位置放置一个障碍，有障碍的地方机器人不能到达），

若是，输出 OK，并且输出从起点到终点（最后落点）的曼哈顿距离，

否则输出 BUG，并且输出第一次能够判断这个命令不是最短路是第几步操作。

其中序列含义如下：

• U 向上移动一格。
• D 向下移动一格。
• L 向左移动一格。
• R 向右移动一格。

输入格式

输入一个长度不超过100的特定字符串其中只包含大写字母UDLR

输出格式

按照题目描述输出

样例 #1

样例输入 #1

LLUUUR

样例输出 #1

OK
4

样例 #2

样例输入 #2

RRUULLDD

样例输出 #2

BUG
7

提示

输入字符串长度不超过 $100$。

第一个测试样例橙色是起点，按照命令走到了蓝色，为了使这条路径成为最短路径我们用白色作为障碍填充就可让这个成为唯一的最短路径。

按照给出的命令行走会出现首尾相接的情况，并且到第7步就已经不能让这个路径成为最短路径了，因为如果第7步之后往其他任何方向移动都可以使起点抄近道而比规定的路径更快。

大大的提示

只要在走的过程中发现上下左右其中一个点在之前已经走过了就不能使这个路径成为最短路，因为可以抄近道走过来。

曼哈顿距离：

在坐标系中两个点$(x1,y1),(x2,y2)$

$dis = |x1-x2|+|y1-y2|$