#P1300. 城市街道交通费系统

城市街道交通费系统

题目描述

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

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

输入格式

输入格式如下:

  1. 第一行有两个整数,地图高度 hh 和宽度 ww
  2. 其后 hh 行,每行 ww 个字符,将是以下字符中的一个:
  • . 表示障碍区。
  • # 表示道路。
  • E 表示起始点且汽车面朝东。
  • W 表示起始点且汽车面朝西。
  • N 表示起始点且汽车面朝北。
  • S 表示起始点且汽车面朝南。
  • F 表示终点。

输出格式

仅包含一个整数,即为最便宜路径的费用。

8 11
...........
....#####..
....#...#..
....#...#..
.#E######..
....#......
.##F#......
...........
8
17 21
.....................
.#######.............
.#.....#.......#.....
.###...#.......#.....
...#...#.......#.....
.###...#.......#.....
.#.....#.......#.....
.############F#####..
.......#..........#..
.......#..........#..
...#...#...#####..#..
...#...#...#.#.#..#..
..#S########.#.#..#..
...#.......#.###..#..
...#.......#......#..
...........########..
.....................
7

提示

样例一解释:

直走,然后左转 33 次,最后右转到终止点 F。如果先直走然后右转 22 次,花费将是 1010


样例二解释:

最便宜的路径花费 77 :立刻左转,直走,在第一个岔路口左转,随后右转。


对于 100%100\% 的数据:4h,w304 \leq h,w \leq 30

数据保证地图中只有一个起点,一个终点,他们之间存在着可通达的路径。同时保证地图最外层一圈都是障碍。