DFS

最少次数，每次都要更新p数组，初始为正无穷

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210;

int n, a, b;
int d[N];
int p[N];
int flag;

void dfs(int u, int level)
{
    p[level] = u;
    if (level == b)
    {
        flag = true;
        return;
    }
    if (level + d[level] <= n && u + 1 < p[level + d[level]])
        dfs(u + 1, level + d[level]);

    if (level - d[level] >= 1 && u + 1 < p[level - d[level]])

        dfs(u + 1, level - d[level]);
}

void solve()
{
    memset(p, 0x3f, sizeof p);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    dfs(0, a);
    if (flag)
        cout << p[b] << endl;
    else
        cout << -1 << endl;
}

int main()
{
    solve();

    system("pause");
    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N=210;
int g[N];
int st[N];
typedef pair<int,int>PII;
int n;

void bfs(int start,int end)
{
	queue<PII>q;
	q.push({start,g[start]});
	st[start]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		int a=t.x-g[t.x],b=t.x+g[t.x];
		if(a>=1&&st[a]==-1){
			q.push({a,g[a]});
			st[a]=st[t.x]+1;
		}
		
		if(b<=n&&st[b]==-1){
			q.push({b,g[b]});
			st[b]=st[t.x]+1;
		}	
	}
}

int main()
{
	int a,b;
	cin>>n>>a>>b;
	
	for(int i=1;i<=n;i++)	cin>>g[i];
	
	memset(st,-1,sizeof st);
	bfs(a,b);
	
	cout<<st[b];
	return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <functional>

using namespace std;

int main() { 
	int n, a, b;
	scanf("%d %d %d", &n, &a, &b);
	
	vector<int> arr(n + 1);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &arr[i]);
	
	long long res = 1e9;
	vector<char> ita(n + 1, 0);
// dfs 好像不行, 这样只有80分
//	long long now = 0;
//	function<void(int)> dfs = [&](int i) { // 递归爆炸 
//		if (i <= 0 || i > n || ita[i])
//			return;
//		
//		if (i == b) {
//			res = min(res, now);
//			return;
//		}
//		
//		++now;
//		ita[i] = 1;
//		dfs(i + arr[i]);
//		dfs(i - arr[i]);
//		ita[i] = 0;
//		--now;
//	};
	
	queue<pair<int, long long>> Q; // 当前是第几层 , 操作次数 
	Q.push({a, 0});
	while (Q.size()) {
		auto x = Q.front();
		int cen = x.first;
		long long cs = x.second;
		Q.pop();
		
		if (cen == b) {
			res = cs;
			break;
		}
		
		if (cen + arr[cen] <= n && !ita[cen + arr[cen]]) {
			ita[cen + arr[cen]] = 1;
			Q.push({cen + arr[cen], cs + 1});
		}
			
		
		if (cen - arr[cen] > 0 && !ita[cen - arr[cen]]) {
			ita[cen - arr[cen]] = 1;
			Q.push({cen - arr[cen], cs + 1});
		}
	}
	
//	dfs(a);
	
	printf("%lld\n", res == 1e9 ? -1 : res);
	
	return 0;
}