首页 > 代码库 > Poj 3669 Meteor Shower

Poj 3669 Meteor Shower

题目大意:

  开始一头牛在 0 0 位置,即为左下角,会有m个陨石落下来,第i个陨石会在ti时刻落在 xi yi 的位置,与其相邻的四个点和其落到的点都会被毁掉,牛想要走到一个永远不回有任何陨石砸到的地方,求走到这个地方的最小时间,如果走不到,则输出-1.

  要求:牛走过的路径上,对于任何一个点,牛到这个点的时刻不得大于等于任何陨石会落在这个点上的时刻。(即,陨石一旦落在某个点上,那么在这个时刻及以后,牛都不可以从这点上走过)

  陨石落下的点的坐标x y均在0-300之间,时间为0-1000之间,m<=5000

 

思路:

  数组Time[x][y]记录点x y被砸到的最早时刻,假如从未被砸到,则设为-1.走的过程中,经过了哪一个点,就把那个点的Time顺便设置为走到那里的最早时刻,因为落下的陨石不会消失,所以假如经过一个地方,就不会需要再回来,因为即便晚点回来,情况也只会变得更糟罢了。

  走到一个Time为-1的地方,则说明到达了安全点。

  因为陨石落下的范围仅仅是0-300 所以如果到了300以外的地方,基本就是是安全的了。

  

  1.给Time标记

  注意标记的时候要判断是否已经被标记过了,如果是的,则更新为较小值。——因为这个地方卡主几次。

  2.把Cow(X=0,Y=0,Time=0)压入搜索队列中,开始搜索。

    每次从队列首提出一个点,假如这个点的到达时刻>=陨石砸到这里的时刻,则不继续搜索,否则,拓展周边四个点。

  3.提取出的队首的点如果陨石砸不到,则搜索到了安全点。