OI题库

【问题描述】

城市街道交费系统最近创立了。一辆汽车左转一次需付费$1，右转一次需付费$5。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费$10。

给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

【样例1】

如下图，符号‘#’代表街道，符号‘.’代表障碍区，符号‘E’表示起始站且汽车面朝东，符号‘F’表示汽车终止点。

...........

....#####..

....#...#..

....#...#．．

.#E######..

....#......

.##F#......

最便宜的路径花费$8：直走，然后左转3次，最后右转到终止点F。如果先直走然后右转2次，花费将是$10。

【样例2】

如图10-2，符号‘S’表示起始站且汽车面朝南。最便宜的路径花费$7：立刻左转，直走，在第一个岔路口左转，随后右转。

.....................

.#######.............

.#.....#.......#.....

.###...#.......#.....

...#...#.......#.....

.###...#.......#.....

.#.....#.......#.....

.############F#####..

.......#..........#..

.......#..........#..

...#...#...#####..#..

...#...#...#.#.#..#..

..#S########.#.#..#..

...#.......#.###..#..

...#.......#......#..

...........########..

.....................

城市地图高度最小为4，最大为30，城市地图宽度亦最小为4最大为30。只有一个起点、一个终点，他们之间总存在可通达的路径。同时由于地图周围一圈均是障碍区，所以汽车是没有可能开除城市的。

【输入】

输入文件erp.in如下：

（1）第一行有2个整数，地图高度h和宽度w。

（2）其后h行每行w个字母，将是以下字母中的一个：

‘.’表示障碍区

‘#’表示道路

‘E’表示起始点且汽车面朝东

‘W’ 表示起始点且汽车面朝西

‘N’ 表示起始点且汽车面朝北

‘S’ 表示起始点且汽车面朝南

‘F’ 表示终点

【输出】

输出文件erp.out仅包含一个整数，即为最便宜路径的费用。

【样例】

erp.in

8 11

...........

....#####..

....#...#..

....#...#..

.#E######..

....#......

.##F#......

...........

erp.out

8