LG#P2895. 流星雨摧毁大农场

流星雨摧毁大农场

题目描述

\hspace{15pt}你位于无限整数网格的原点 (0,0)(0,0),只能在横、纵坐标均非负的区域活动。时刻 00 开始行动,每经过一个单位时间,可向上下左右相邻的一个格子移动一步。

\hspace{15pt}有 kk 颗流星。第 ii 颗流星在时刻 tit_i 落到 (xi,yi)(x_i,y_i),使该格和上下左右相邻的格子永久毁灭,负坐标格子无需考虑。多次波及同一格子时,以最早的毁灭时刻为准。

\hspace{15pt}若某格在时刻 tt 毁灭,就只能在严格早于 tt 的时刻位于该格;因此不能在流星落下的同一时刻进入该格。请计算到达一个永远不会毁灭的格子所需的最短时间。若原点永远安全,答案为 00;若无法逃到安全格子,答案为 −1-1。

输入格式

\hspace{15pt}第一行输入一个整数 k(1≦k≦5×104)k\left(1\leqq k\leqq5\times10^4\right)。

\hspace{15pt}此后 kk 行,每行输入三个整数 $x_i,y_i,t_i\left(0\leqq x_i,y_i\leqq300;\ 0\leqq t_i\leqq10^3\right)$,代表流星位置与坠落时刻。流星记录不保证按时间排序,位置和时间均允许重复。

\hspace{15pt}可移动区域没有以 300300 为界的边界;该上界只约束流星中心坐标。

输出格式

\hspace{15pt}输出到达永远安全格子的最短时间;无法到达时输出 −1-1。

测试样例

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

样例 1 解释

\hspace{15pt}可以依次到达 (0,1),(0,2),(0,3),(0,4),(0,5)(0,1),(0,2),(0,3),(0,4),(0,5),对应时刻为 1,2,3,4,51,2,3,4,5。每一步都严格早于该格的毁灭时刻,且 (0,5)(0,5) 永远安全;广度优先搜索可验证不存在更早的安全到达方案。

1
0 0 0
-1