回溯不是跑很慢的吗,那个大佬帮蒟蒻解释一下...
61ms...
#include <iostream>
using namespace std;
int n,x,y,floor[205];
bool vis[205];
int ans=1e9;
bool check(int x){
if(x<1||x>n||vis[x])return false;
return true;
}
void dfs(int x,int y,int sum){
if(x==y){
ans=min(ans,sum);
return ;
}
if(sum>ans){
return ;
}
vis[x]=true;
if(check(x+floor[x])) dfs(x+floor[x],y,sum+1);
if(check(x-floor[x])) dfs(x-floor[x],y,sum+1);
vis[x]=false;
}
int main(){
cin>>n>>x>>y;
for(int i=1;i<=n;i++)cin>>floor[i];
dfs(x,y,0);
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}