这是我的代码(就是一个裸 dfs):

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f
const int MAXN = 200 + 5;
int k[MAXN], n, a, b, ans;
bool vis[MAXN];

int dfs(int cur, int cnt) {
  if (cur == b)
    return cnt;
  int up = cur + k[cur], down = cur - k[cur];
  int upcnt = inf, downcnt = inf;
  if (up <= n && !vis[up]) {
    vis[up] = true;
    upcnt = dfs(up, cnt + 1);
    vis[up] = false;
  }
  if (down >= 1 && !vis[down]) {
    vis[down] = true;
    downcnt = dfs(down, cnt + 1);
    vis[down] = false;
  }
  return min(upcnt, downcnt);
}

int main() {
  cin >> n >> a >> b;
  for (int i = 1; i <= n; i++)
    cin >> k[i];
  vis[a] = true;
  ans = dfs(a, 0);
  if (ans == inf) cout << -1;
  else cout << ans;
  return 0;
}

第 8、9 个点 TLE 了, 下载数据看发现是死循环

150 1 150
1 1 26 7 9 21 10 5 12 13 3 15 3 26 2 9 28 12 24 10 21 26 22 10 5 10 14 8 25 9 15 5 27 9 24 30 15 27 25 1 5 5 16 1 18 1 24 20 24 22 17 7 21 18 29 20 30 8 21 9 3 24 15 27 16 18 29 21 11 1 22 30 24 23 6 5 28 24 18 26 21 9 3 19 9 27 5 9 17 29 6 5 9 6 18 15 9 5 19 23 23 3 3 2 4 24 25 12 19 14 23 15 11 25 25 5 3 3 2 6 21 7 18 8 11 26 10 10 20 21 28 10 15 9 24 23 17 22 13 17 18 27 21 4 15 13 4 2 1 0

于是加了一个剪枝,

if (cnt >= mincnt)
    return inf;

这次 AC 了. 但是我不太明白为什么没加剪枝会死循环. 按照道理来说, 没加剪枝慢归慢, 应该不会死循环的.

翻了翻评论区发现很多 80分 TLE 的求助都和我一样的问题, 就是死循环; 解决方案无外乎是改 bfs 或者剪枝, 但是就是不知道为什么会死循环.

跪求路过的大佬予以解惑! 在线等, 也不是特别急