题目描述 独轮车是一种仅有一个轮子的特殊自行车。他的轮子被等分成5个扇形,分别涂上一种不同的颜色。现在有一个人骑自行车行驶在M*N的网格平面上。每个格子的大小恰好使得当车从一个格子骑到下一个格子时,轮子恰好转过一个扇形。
如下图所示,当轮子在1号格子的中心时,蓝色扇形的外弧线中线刚好于地面接触。当它移动到下一个格子(2号格子)的时候,白色扇形的外弧线于地面接触。
有些各自中有障碍,所以车子不能通过这些格子。骑车人从某个格子出发,希望用最短的时间移动到目标格。在任何一个格子上,他要么骑到下一个格子,要么左转或者右转90度。其中每项动作恰好需要1秒来完成。初始时,他面朝北且绿色扇形贴着地面。到达目标格时,也必须是绿色扇形贴着地面,但朝向无限制。如下图所示。
输入数据 有多组测试数据,每组格式如下: 第一行包含两个整数M和N(1<=m,n<=25),表示迷宫的行数和列数,接下来是网格的描述,用M行长度为N的字符串来表示。字符#表示一个障碍方格,其他方格均可通行。骑车人的起点用S表示,终点用T表示。 输入结束标志是m=n=0。
输出数据 对于每组测测试数据: 输出测试数据编号和到达目标格的最短时间(单位:秒)。如果无法到达,输出“destination not reachable”。相邻两组输出空行。