luogu#P4872. OIer们的东方梦

    ID: 8898 远端评测题 1000ms 128MiB 尝试: 4 已通过: 2 难度: 5 上传者: 标签>洛谷原创O2优化广度优先搜索BFS优先队列队列

OIer们的东方梦

题目背景

#11,#12 两组 Hack 数据由 uid=20285 提供

OIer 们做魂魄妖梦都想去幻想乡玩一下。这一次,他们在睡古明地觉时在梦中穿越去了幻想乡,幻想乡有很多的少(ju)女(ruo),但是他们被老太婆少女的美色和蒟蒻的美味所吸引,在幻想乡中迷失了方向。

勇敢的死肥宅少年啊,现在你手里有一份幻想乡人间之里的地图,你知道 OIer 们的位置,你可以远程给OIer们传递信息,请你带领迷路的 OIer 们走进回到现实生活的祭坛吧!

题目描述

给你一个 N×MN\times M 的地图,如图所示:

5400000S01     
1111101101     
000003X301      
3111111101     
E000300031      
1111X30001     

其中有很多稀奇古怪的东西:

  • SS 表示出发点,EE 表示终点。
  • 00 表示空地,你想怎么走就怎么走,走一格需要 1s1s
  • 11 表示墙,你无法通行(除非你受到了风神少女的庇护)。
  • 22 表示小妖怪,你需要 3s3s 的时间去消灭小妖怪,才能经过该位置。(PS: 妖怪被消灭后只要离开当前格子立刻复活)
  • 33 表示大妖怪,你需要 8s8s 的时间去消灭大妖怪,才能经过该位置。
  • 44 表示太阳花田,到达该位置可以获得太阳花,获得太阳花后遇到妖怪时可直接通过该妖怪的位置。
  • 55 表示楼观剑(科普君:楼观剑,英文名 Louguan is very jianLouguan\ is\ very\ jian,是妖怪做的剑,楼观剑斩不断的东西几乎没有),到达该位置可以花费 5s5s 获得它,获得它后可以砍墙砍妖怪将其变成空地(当然也可以不砍,砍墙砍妖怪不需要时间,楼观剑可以一直使用不会损坏,有了楼观剑依然可以使用隙间,但是楼观剑不能砍隙间和一点用都没有的麻薯,麻薯妖梦UUZ是一家嘛
  • MM 表示麻薯(是 mashumashu 不是 mafumafu不知道麻薯是什么的一把楼观剑给你砍过来),碰到麻薯后你可以把它吃了(路人甲:那你为什么还要加这个东西? 出题人:有 SS 肯定要有 MM 啊。路人乙:我就是死外边,从隙间中跳下去,也不会吃麻薯!嗯~真香!)
  • XX 表示紫妈的隙间,碰到隙间后会传送至其他的任意一个隙间(数据保证只有 0 或 2 个隙间,就是说可以有很多隙间乱传),每次传送耗时 1s1s。(经过当前格子时可以不经过隙间)

答案输出 OIer 们到达终点所需最短时间。如果无法到达,输出 "We want to live in the TouHou World forever"。
翻译:此生无悔入东方,来世睡遍愿生幻想乡。

温馨提示:不排除存在可以往回走等稀奇古怪的最优走法

输入格式

数据共有 N+1N+1行。

11 行输入 NNMM
22N+1N+1 行输入 N×MN\times M 的地图。

输出格式

一行,最短时间或者 "We want to live in the TouHou World forever"。

6 10
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001
16
5 10
S23323323X
2032332333
1202202202
1111111111
11111111XE
44
9 10
SX1X0X1X1X
2332332333
5205205200
XXXXXXXXXX
2222222222
3333333333
3333333333
XXXXXXXXXX
XXXXXXXXXE
3

提示

对于 30%30\% 的数据,1N,M501\leq N,M\leq 50
对于 50%50\% 的数据,1N,M1001\leq N,M\leq 100
对于 100%100\% 的数据,1N,M10001\leq N,M\leq 1000

保证有一组数据答案为 "We want to live in the TouHou World forever",数据有梯度。

样例解释

样例 1:在 7s7s 时到达楼观剑,在 12s12s 时获得楼观剑,一路向下砍到达终点。
样例 2:在 10s10s 时到达 (3,3)(3,3),在 32s32s 时到达(3,10)(3,10),向上进入隙间后到达终点。
样例 3:这个就不用解释了吧(出题人放飞自我)。