大逃亡

发布时间: 2017年11月12日 20:06   最后更新: 2017年11月12日 20:08   时间限制: 1000ms   内存限制: 512M

计算机之神正在玩一个惊险刺激的游戏,在游戏中主人公HS处在一片极端不稳定的地带。这片地带可以用平面直角坐标系来描述,在时刻Ti,坐标点(Xi,Yi)将会发生严重的地面塌陷,连同这个点上下左右四个相邻点(Xi+1,Yi),(Xi-1,Yi),(Xi,Yi+1),(Xi,Yi-1)也将会塌陷。

初始时刻0HS处在(0,0)位置,他只能平行于坐标轴移动并且移动到相邻坐标点需要1个单位时间。现在HS要尽快抵达一个位于第一象限或在坐标轴正半轴上的永远不会塌陷的坐标点(x,y),在他逃亡的过程中不能经过已经发生塌陷的坐标点,且任意时刻他所在位置的两个坐标都必须非负。

计算机之神想考考你HS能否逃到安全的地方,若能输出最短时间,否则输出-1

第一行为一个整数T(T<=15),表示数据组数。
接下来T组数据每组数据第一行输入一个整数M(M<=50000),表示将会发生M次塌陷。
接下来M行每行三个整数Xi,Yi(0<=Xi,Yi<=300),Ti(0<=Ti<=1000),表示在时刻Ti时位置(Xi,Yi)会发生塌陷。

输出T行,每行一个整数代表最少要花多少时间到达安全区域,如果无法到达安全区域则输出-1。

复制
1
4
0 0 2
2 1 2
1 1 2
0 3 5
5

一种可行的躲避方案:(0,0) -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4)

搜索

2017 Fudan ACM-ICPC 程序设计校赛网络赛