P1300 城市街道交通费系统

    • 96通过
    • 246提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    城市街道交费系统最近创立了。一辆汽车左转一次需付费$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’ 表示终点

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    8 11
    ...........
    ....#####..
    ....#...#..
    ....#...#..
    .#E######..
    ....#......
    .##F#......
    ...........
    
    输出样例#1: 复制
    8
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。