#85. 奇怪的电梯

奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 ii 层楼(1iN1≤i≤N)上有一个数字 Ki(0KiN)K_i(0≤K_i≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:从一楼开始,3 3 1 2 5代表了 Ki(K1=3,K2=3,)K_i(K_1=3,K_2=3,……) 。在一楼,按“上”可以上 3 层到 4 楼,按“下”是不起作用的,因为没有 -2 楼。那么,从 A 楼到 B 楼至少要按几次按钮呢?

输入格式

输入共有二行,第一行为三个用空格隔开的正整数,表示 N,A,BN,A,B,第二行为 NN 个用空格隔开的正整数,表示 KiK_i

输出格式

输出仅一行,即最少按键次数,若无法到达,则输出 -1。

样例输入与输出

5 1 5
3 3 1 2 5
3

样例解释

输入解释

第一行的数据 5表示总共5层楼,第二个数据1表示初始在1楼,第三个数据5表示我们最终的目的地是5楼。
第二行的数据 第二行输入了5个数,分别表示每一层的电梯能上下几层。
第一个数3 表示在1楼可以上3层楼,到达4楼;也可以下3层楼,但是我们没有-2层楼,所以从1楼下3层不行。
第二个数3 表示在2楼可以上3层楼,到达5楼;也可以下3层楼,但是我们没有-1层楼,所以从2楼下3层不行。
第三个数1 表示在3楼可以上1层楼,到达4楼;也可以下1层楼,到达2楼。

输出解释

那么我们初始在1楼,只能上3层到达4楼,在4楼只能下2层到达2楼,然后上3层到达5楼。总共用了3步,所以最终输出3。

数据范围

对于 100% 的测试数据满足:1N200,1A,BN1≤N≤200, 1≤A,B≤N