本题没有可用的提交语言。

题目描述

阿夫申披萨连锁店$（Afshung - Pizza chain）$是希尔达维亚$（Sildavya）$地区哈梅东$（Hamedung）$的一家提供上门披萨配送服务的公司，它需要你帮忙制定最快的披萨配送方案。每个配送员都配备了一台能显示哈梅东所有街道的地理信息系统$（GIS）$设备，通过该设备，他们可以找到一条将披萨送到订单地点的快速路线。销售并维护这一 $GIS$ 设备的埃利亚松公司$（Elyasung Company）$需要你重新编写设备程序，以提供更快的路线规划。

哈梅东是一个矩形区域，有许多双向的直线街道。$GIS$ 设备使用文本字符来展示地图，如示例测试数据所示。在这种格式中，每一公里的街道用横线（-）或竖线（|）表示，分别代表街道是东西走向还是南北走向。地图上的加号（+）表示在该位置有一个 $90$ 度的急转弯（长度为零），且没有交通信号灯，所有此类转弯都用 + 标记。十字路口用一个整数 $τ$ 表示，$τ$ 是该十字路口交通信号灯的计时时间，十字路口可以是三路或四路的。为了使该地区交通顺畅且无事故，哈梅东市政府规定，每个交通信号灯在三路或四路十字路口分别只有一个绿灯和两个或三个红灯。十字路口的某一个方向的信号灯会在 $τ$ 分钟内保持绿灯（即，在某个时间区间 $[x, x + τ)$ 内），其他方向为红灯。接下来的 $τ$ 分钟，另一个方向变为绿灯，就好像绿灯是逆时针转动一样。所有十字路口都遵循此规则。

当配送员开始出发时，时间设为零。此时，所有交通信号灯都设置为每个十字路口只有朝南的信号灯（如果没有朝南的信号灯，则为朝北的信号灯）为绿灯，该十字路口的其他信号灯为红灯。

请注意，司机只能在转弯处（+）或十字路口（用数字表示）改变行驶方向。例如，如果地图上有 -|- 这样的图案，司机从左向右或从右向左行驶时不能穿过竖线，也不能向左或向右转，因为该位置没有十字路口。

给定上述完整的地图、标有 S 的阿夫申披萨店的位置以及标有 D 的最终配送地点的位置，你需要为 GIS 设备编写一个程序，自动找出从 S 到 D 最快的可能路线。请注意以下假设：

• S 和 D 是街道的一部分（替代 - 或 |）。
• S 和 D 不与任何十字路口或转弯处相邻。
• S 和 D 彼此不相邻。
• 十字路口和/或转弯处至少相距一公里。
• S、D、+ 和每个数字所代表的位置长度为零。
• 配送员的速度是每分钟一公里。
• 面对绿灯的车辆可以向所有方向行驶。红灯时不允许直行或转弯。
• 途中没有交通堵塞或其他障碍物。
• 星号字符（*）表示该地区的边界。

输入

输入文件的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量，随后是每个测试用例的输入数据。每个测试用例的第一行包含两个整数：$N$（$1 \leq N \leq 100$），表示地图的行数；$M$（$2 \leq M \leq 100$），表示地图的列数。第一行之后会有 $N$ 行，每行包含一个长度为 $M$ 的字符串，由 -、|、+、 、*、S、D 或 1 到 9 的数字组成。此外，假设十字路口和转弯处（+）的总数最多为 $100$。

输出

每个测试用例的输出应该有一行，包含一个数字，表示从 S 到 D 的最短行驶时间（如果存在）；否则输出单词 impossible（小写字母）。

输入样例

1 
10 10 
********** 
*-D-3---+* 
*   |   |* 
*   | +-+* 
*   |-|  * 
*---4-1- * 
*   | |  * 
*   | |  * 
*S--2-+  * 
********** 

输出样例

15

题目来源

德黑兰 2002 年竞赛题目