#P3383. [Usaco2004 Open]Cave Cows 4 洞穴里的牛之四

    ID: 2573 传统题 1000ms 512MiB 尝试: 50 已通过: 25 难度: 4 上传者: 标签>难度分类普及枚举与搜索广度优先搜索数据结构有序集合状态去重CF1400Orange

[Usaco2004 Open]Cave Cows 4 洞穴里的牛之四

[USACO 2004 Open] Cave Cows 4 洞穴里的牛之四

题目描述

岩石崩塌把贝茜困在洞里。她必须攀上一面竖直岩壁才能脱困。把岩壁视为 xzxz 平面,xx 轴水平,zz 轴向上。她从 (0,0)(0,0) 出发,只要到达任意一个高度为 TT 的落蹄点,就能越过岩壁。

岩壁上有 NN 个能落蹄的突起。一次移动时,新落蹄点与当前位置的 xx 坐标之差的绝对值以及 zz 坐标之差的绝对值都不能超过 22。她既可以向上或横向移动,也可以向下移动。

求她能否到达岩壁顶部,以及所需落蹄点的最少数量。

输入格式

从标准输入读入。第一行是两个整数 N,TN,T。接下来 NN 行,每行两个整数 x,zx,z,表示一个落蹄点的坐标。

输出格式

向标准输出输出一行一个整数。如果能到达顶部,输出最少步数,起始位置不计一步;否则输出 −1-1。

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

样例解释

一条最短路线是 (0,0)→(1,2)→(3,2)→(4,1)→(6,3)(0,0)\to(1,2)\to(3,2)\to(4,1)\to(6,3),共 44 步。

数据范围与约定

1≤N≤50 0001\le N\le50\,000,1≤T≤200 0001\le T\le200\,000,0≤x≤1060\le x\le10^6,0≤z≤T0\le z\le T。输入的落蹄点不含 (0,0)(0,0)。