UVA12807 GPS

题意 ======== 根据矩阵地图，写一个导航系统。**星号**表示可以走的路，**空格**表示不能走的障碍。提供起点和终点的坐标，要求求出最短路。每次移动只能向上下左右四个方向走。如果有多条最短路，向四个方向走的优先级分别是 右>下>左>上。选择优先级最高的方向移动。 地图周围一圈是装饰性的，应当忽略，不计入实际地图。

第一行一个整数表示数据组数。 每一组数据中，第一行两个整数分别表示**除去装饰性边框不算，地图余下部分的宽和高。** 接下来给出地图，总共有`宽+2`列和`高+2`行，多出的两行两列是装饰性边框，应当忽略。除去边框后，图的左上角是(0,0)点。 最后给出起点和终点的坐标。

每组数据第一行，输出 > Turn to the 东西南北. 接下来每行给出的导航信息可以是： 1. Turn left. 左转 2. Turn right. 右转 3. Continue $x$ km. 前进x格 最后一行应该是： > You have reached your destination. 您已经到达目的地了。 每组数据的回答输出完毕后要额外输出一个空行来间隔不同数据。特别地，最后一组数据结尾也要输出这个空行。也就是说在整个文件结尾有连续两个换行符。**行数不对是直接WA的。**

每一组数据中，第一行两个整数分别表示**除去装饰性边框不算，地图余下部分的宽和高。** 接下来给出地图，总共有`宽+2`列和`高+2`行，多出的两行两列是装饰性边框，应当忽略。除去边框后，图的左上角是(0,0)点。 最后给出起点和终点的坐标。 由 @WuTianming 提供翻译