游客 注册 | 登录
中文 | En

1770 - 奇怪的电梯

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

Input

输入文件共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)，第二行为N个用空格隔开的正整数，表示Ki。 
Output

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

Sample Input


5 1 5
3 3 1 2 5

Sample Output


3

题目输入

题目输出

输入/输出样例

输入格式


                        

                        

                            
输出格式

                            

                        


                        
                                            


                                        
                    

						                                                            
C语言解答

                                
#include<stdio.h>  
#define INT_MAX 99999  
int g[300][300];  
int a,b,n,k;  
int main()  
{  
	int i,j;
    scanf("%d%d%d",&n,&a,&b);  
     for (i=1;i<=n;++i)  
        for (j=1;j<=n;++j)  
            g[i][j]=INT_MAX;  
    for (i=1;i<=n;++i)  
    {  
        g[i][i]=0;  
        scanf("%d",&k);  
        if (i+k<=n) g[i][i+k]=1;  
        if (i-k>0)  g[i][i-k]=1;  
    }  
    for (k=1;k<=n;++k)  
    	for (i=1;i<=n;++i) 
			if (i!=k)  
            for (j=1;j<=n;++j) 
			if((i!=j)&&(j!=k))  
                 if (g[i][j]>g[i][k]+g[k][j])  
                    g[i][j]=g[i][k]+g[k][j];  
     if (g[a][b]==INT_MAX) 
		printf("-1\n");  
     else 
	 printf("%d\n",g[a][b]);  
     return 0;  
}  




                                                        
                                                            
C++解答

                                
#include <iostream>
#include <limits.h>
#include <cstring> 
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;i++) 
#define M 250
int A,B,n;
int s[M],d[M];
bool b[M];
int t[M],head=0,tail=1;
int main()
{
	cin>>n>>A>>B;
	F(i,1,n)
	{
		cin>>s[i];
	}
	memset(b,0,sizeof(b));
	F(i,0,n)
	{
		d[i]=INT_MAX;
	}
	t[1]=A;
	b[A]=1;
	d[A]=0;
	do
	{
		head=(head+1)%M;
		int u=t[head];
		b[u]=0;
		int v1=u+s[u],v2=u-s[u];
		if (v1<=n && d[v1]>d[u]+1)
		{
			d[v1]=d[u]+1;
			if (!b[v1])
			{
				tail=(tail+1)%M;
				t[tail]=v1;
				b[v1]=1;
			}
		}
		if (v2>0 && d[v2]>d[u]+1)
		{
			d[v2]=d[u]+1;
			if (!b[v2])
			{
				tail=(tail+1)%M;
				t[tail]=v2;
				b[v2]=1;
			}
		}
	}while(head!=tail);
	
	if (d[B]==INT_MAX) cout<<-1;
	else cout<<d[B];
	return 0;
}




                                                                                    
                                                                        
                    
                
                
            

            

                

                

                    

                        







                    


                    

                        请先登陆