LG#P2895. 流星雨摧毁大农场
流星雨摧毁大农场
题目描述
你位于无限整数网格的原点 ,只能在横、纵坐标均非负的区域活动。时刻 开始行动,每经过一个单位时间,可向上下左右相邻的一个格子移动一步。
有 颗流星。第 颗流星在时刻 落到 ,使该格和上下左右相邻的格子永久毁灭,负坐标格子无需考虑。多次波及同一格子时,以最早的毁灭时刻为准。
若某格在时刻 毁灭,就只能在严格早于 的时刻位于该格;因此不能在流星落下的同一时刻进入该格。请计算到达一个永远不会毁灭的格子所需的最短时间。若原点永远安全,答案为 ;若无法逃到安全格子,答案为 。
输入格式
第一行输入一个整数 。
此后 行,每行输入三个整数 $x_i,y_i,t_i\left(0\leqq x_i,y_i\leqq300;\ 0\leqq t_i\leqq10^3\right)$,代表流星位置与坠落时刻。流星记录不保证按时间排序,位置和时间均允许重复。
可移动区域没有以 为界的边界;该上界只约束流星中心坐标。
输出格式
输出到达永远安全格子的最短时间;无法到达时输出 。
测试样例
4
0 0 2
2 1 2
1 1 2
0 3 5
5
样例 1 解释
可以依次到达 ,对应时刻为 。每一步都严格早于该格的毁灭时刻,且 永远安全;广度优先搜索可验证不存在更早的安全到达方案。
1
0 0 0
-1