https://www.luogu.org/problem/P1135
# include <iostream> #include<cstring> #include<string> #include<vector> #include<cmath> #include<stack> #include<strstream> #include<queue> #include<cstdio> #include<algorithm> using namespace std; int n, st, ed; int a[301]; bool mark[301]; int minsum = 999999999; void dfs(int now, int nowsum) { if(now == ed) { if(nowsum < minsum) minsum = nowsum; return ; } if(nowsum >= minsum ) return ; //mark[now] = true; if(now + a[now] <= n && !mark[now + a[now]])//往上搜索 { mark[now] = true; dfs(now + a[now], nowsum + 1); mark[now] = false; } if(now - a[now] >= 1 && !mark[now - a[now]])//往下搜索 { mark[now] = true; dfs(now - a[now], nowsum + 1); mark[now] =false; } //mark[now] = false; } int main() { cin>>n>>st>>ed; for(int i = 1; i <= n; i++) cin>>a[i]; dfs(st, 0); if(minsum != 999999999) cout<<minsum<<endl; else cout<<-1<<endl; // system("pause"); }
