目前被困在迷宫机器人。现在你必须要发出一些指令,告诉它如何到达目的地。
迷宫是一个m *不发车。对一些牢房是空的,有些则占领了墙上。当然,机器人不能移动到墙上,和机器人还不能在网格移动外也。该机器人只能接受三个命令:左转,右转。这个机器人可能面临北,南,东或西运动期间。当它收到左转命令,它会旋转90度到左边。也就是说,如果向东面临命令之前,将面对后左转命令北部。在右转命令几乎相同,只是方向是相反的。当收到GO命令,机器人将走向它的方向1个单位,除非有在它前面空细胞。
请注意机器人总是面对一开始,即在面对迷宫地图上的边界以北。 (迷宫图将说明如下。)
您想使用最少的指令,所以你应该写一个程序的帮助。
输入格式:(b3.in)
在输入的第一行是测试的个案。
每个测试案例的第一行包含两个整数M和N,表明迷宫的大小。有M线后,每行正好包含N个字符,描述的M *不迷宫。在'#',显示墙,'。显示空单元格,了'S'和'T'表示的开始点和目的地分别机器人。还有迷宫地图在任何其它字符。
在迷宫地图定位只是作为常识一样。也就是说,左上角的迷宫角落地图,标明西北方向,右下角显示东南部。
你可以假设1≤M≤100和1≤ñ≤100。只有一个'S'和一个'T的迷宫'。
输出格式:(b3.out)
输出一行为每个测试案例,表明所需要的最低数量的指示。或输出-1,如果这是不可能实现机器人的目的地。
示例输入:
此题英文翻译,供编程高手参考