UPC-穿越

山再高,往上爬,总能登顶;
路再长,走下去,定能到达。

穿越-时间轴上的bfs

题目描述

亚马逊雨林实在是太大了,小X和他的小弟们进去一会儿就迷路了,然而大雨已经来临,冲刷了一些道路,小X凭借他最后的5%的电量给你发来一条求助信息,希望你帮助他们逃出困境……
小X给你发来一张n×m的地图,每一个点有4种情况。
“0”:此地方可以走。
“1”:此地方不可以走。
“2”:此地方有一种凶恶的野兽。
“3”:此地方为传送地域。
野兽会不定时地苏醒过来,此阶段该处就不能走。
暴雨会不定时地冲刷一些地区,这些地区从今往后不可以行走,也不可以传送到。
传送地域之间可以互相传送,即可以从一个传送门传送到任何一个其他的传送门。
小X和他的小弟们现在位于(1,1),他们希望在(n,m)点逃出雨林。
他们只能前后左右移动,每移动一次需要花费1个单位的时间,传送一次需要花费2个单位的时间,也可以选择不传送。
注意:若下一秒某地区暴雨即将冲刷/野兽即将醒来,则不可以通行,也不可停留在这个这个地区。
在任意时刻,他们可以选择不进行任何操作。

输入

第一行两个整数n,m,表示一张n×m的地图。
接下来n行,每行m个整数,为0-3之间的一个数字。
接下来一行一个整数a,表示接下来a行描述暴雨情况。
接下来a行,每行第一个整数为t,表示此次暴雨在t时刻来临;第二个整数为p,表示此次暴雨冲刷了p个地区;接下来p组整数,每组有(x,y)两个整数,表示(x,y)这个地点被冲刷。(假设暴雨冲刷不需要时间,同一个地点可能被暴雨多次冲刷)
接下来b行,每行前两个整数为t1,t2,表示这个野兽在t1-t2时刻是苏醒的。接下来两个整数x,y,表示野兽位于x,y位置。(保证(x,y)=2)
不保证所有的野兽均会有苏醒的时刻
保证:(1,1)=(n,m)=0且永远不会被暴雨冲刷。

输出

一行一个整数,即最短逃脱时间。
(保证小X和他的小弟们可以逃脱亚马逊雨林)

Sample Input

3 3
0 1 0
2 0 1
3 2 0
2
2 1 3 1
1 1 1 3
1
2 4 2 1

Sample Output

4

Hint

时刻1,暴雨冲刷了1,3这个位置。
时刻2,暴雨冲刷了3,1这个位置。
时刻2-4,位于(2,1)的野兽苏醒了。
小X与他的小弟们的逃脱路线:
(1,1)->(2,1)->(2,2)->(3,2)->(3,3)
【数据范围】
对于100%的数据,n≤300,m≤300,t≤10000。

首先感谢一波CoolGuang学长的耐心教学。
我不生产知识我只是知识的搬运工。。。
思路分析
这是一个时间轴上的bfs,那么时间尤为重要。而普通bfs中第一个到达就最优的做法就显得有些不妥。用更新最有时间的方法来,可以很好的解决多个传送门何时到的问题,以及可以什么时候到的问题。直接第一个到达的话很难控制时间。
我门可以吧传送门专门存起来,因为传送门都可以互相传送,如果可以传送的话,这样的话我们需要遍历所有传送门更新最优解。
洪水假设我们终将都会到来,只是有的到来的时间无穷大,有的很接近现在而已
然后我们也就是分类讨论
1.空地
2.有野兽
3.传送门
传送门已经说过了,前提是你必须得在可以传的条件下传
而且你得分成我走不走传送门
空地直接更新最优解就

上一篇:11C:寻找边缘


下一篇:搜索之走迷宫|题解