#P3383. [Usaco2004 Open]Cave Cows 4 洞穴里的牛之四
[Usaco2004 Open]Cave Cows 4 洞穴里的牛之四
[USACO 2004 Open] Cave Cows 4 洞穴里的牛之四
题目描述
岩石崩塌把贝茜困在洞里。她必须攀上一面竖直岩壁才能脱困。把岩壁视为 平面, 轴水平, 轴向上。她从 出发,只要到达任意一个高度为 的落蹄点,就能越过岩壁。
岩壁上有 个能落蹄的突起。一次移动时,新落蹄点与当前位置的 坐标之差的绝对值以及 坐标之差的绝对值都不能超过 。她既可以向上或横向移动,也可以向下移动。
求她能否到达岩壁顶部,以及所需落蹄点的最少数量。
输入格式
从标准输入读入。第一行是两个整数 。接下来 行,每行两个整数 ,表示一个落蹄点的坐标。
输出格式
向标准输出输出一行一个整数。如果能到达顶部,输出最少步数,起始位置不计一步;否则输出 。
5 3
1 2
6 3
4 1
3 2
0 2
4
样例解释
一条最短路线是 ,共 步。
数据范围与约定
,,,。输入的落蹄点不含 。