LG#P1135. 奇怪的电梯

奇怪的电梯

题目描述

\hspace{15pt}一栋楼有 nn 层,编号为 1∼n1\sim n。第 ii 层写有整数 kik_i。

\hspace{15pt}位于第 ii 层时,可以按一次向上按钮到达第 i+kii+k_i 层,或按一次向下按钮到达第 i−kii-k_i 层。若目标不在 1∼n1\sim n 范围内,这个方向不能使用;到达新楼层后,下一次移动使用新楼层对应的数值。

\hspace{15pt}求从第 aa 层到第 bb 层最少需要按多少次按钮。若起点就是终点,可以不按按钮。

输入格式

\hspace{15pt}第一行输入三个整数 $n,a,b\left(1\leqq n\leqq200;\ 1\leqq a,b\leqq n\right)$。

\hspace{15pt}第二行输入 nn 个整数 k1,k2,…,kn(0≦ki≦n)k_1,k_2,\dots,k_n\left(0\leqq k_i\leqq n\right)。

输出格式

\hspace{15pt}输出最少按钮次数;无法到达时输出 −1-1。

测试样例

5 1 5
3 3 1 2 5
3

样例 1 解释

\hspace{15pt}可以按顺序经过楼层 1→4→2→51\to4\to2\to5,分别使用当前楼层的步长 3,2,33,2,3,共按 33 次按钮。这也是最少次数。

3 1 3
0 1 2
-1