https://www.luogu.org/problem/P1135

Title Description

Well, one day I had a dream and dreamed of a strange elevator. The elevator can be stopped on each floor of the building, and there is a number Ki(0 less than Ki = N) K_i (0 \le K_i \le N) on the I floor (1 I) or N (0). The elevator has only four buttons: turn on, off, up and down. The number of floors above and below is equal to the number on the current floor. Of course, if it fails to meet the requirements, the corresponding button will fail. For example: 3, 3, 1, 2, 5 represents Ki(K1=3,K2=3,... ) K_i(K_1=3,K_2=3,... ) Ki(K1=3,K2=3,... From the first floor. On the first floor, press "up" to the fourth floor, press "down" does not work, because there is no 2 floor. So how many buttons do you have to press at least from Building A to Building B?

Input format

A total of two lines.

The first behavior consists of three positive integers separated by spaces, representing N, A and B (1 < N < 200, 1 < A,B < N).

The second behavior is N non-negative integers separated by spaces, representing KiK_iKi.

Output format

One line, that is, the minimum number of keystrokes, if not reached, then output 1.

Input and Output Samples

Input #1

5 1 5
3 3 1 2 5

Output #1

3

Code

#include<cstdio>
#include<iostream>
using namespace std;

int n,st,ed,p=0,i,j;

//St start
//End of ED

int step[210],lift[210];
//How many times have step numbers been pushed to Layer i?
//lift what is the key button on elevator i?

bool pd=true;//pd=true can go or can't go
int main()
{
    scanf("%d %d %d",&n,&st,&ed);
    for(i=1;i<=n;i++) 
    {
        step[i]=-1;
        //Let me first set the number of steps to -1.
        //- 1 means no passing        
        scanf("%d",&lift[i]);
        //Elevator upper (lower) storeys
    }
    step[st]=0;
    //Start step 0
    while(step[ed]==-1 && pd)
    //When the last layer is not accessed
    //pd is explained below 
    {
        pd=false;//Let's assume we can't go.
        for(i=1;i<=n;i++)//Layer by layer simulation
            if(step[i]==p) //The first time p is 0, step[st] starts to run, P plays a more important role.
            {
                j=i+lift[i];//Simulated upstairs
                if(j<=n && step[j]==-1)//No more than n floors and no passing
                {
                    step[j]=p+1;//If you walk here, look for this floor next time. 
                    pd=true;//If you can't walk, go to the next level for assuming that the dead cycle is pd=false, jump out while 
                }
                
                j=i-lift[i];//Simulated downstairs 
                if(j>0 && step[j]==-1)//Not underground and not through.
                {
                    step[j]=p+1;
                    pd=true;//The same way upstairs
                }
            }
        p++;//Next floor 
    }
    printf("%d",step[ed]);//The step[ed] does not change if it does not go through, so the step output is the same if the - 1 changes.
    return 0;
}