如果dfs不加 vis 会MLE,加上会有TLE+MLE,再加上如果超过当前答案就 return 的优化也会造成前 6 个测试点TLE
附我的DFS代码,佬们可以看看还能怎么优化:
#include <bits/stdc++.h>
using namespace std;
int k[205],g[205],b,n,ans = 0x7ffffff,cnt1;
bool f[205];
void dfs(int c,int s,int cnt){
//if (++cnt1 > 1e6) return;数据加强前为了过#1需要加上这个卡一下,现在加这个会前6点WA,可知前6点都需要递归1e6次+;
if (cnt > ans) return;//最短优化
if (c == b) {
ans = min(ans,cnt);
return;
}
f[c] = true;//相当于vis数组
if (c - s > 0 && !f[c-s]) dfs(c - s,k[c-s],cnt + 1);
if (c + s <= n && !f[c+s]) dfs(c + s,k[c+s],cnt + 1);
f[c] = false;
}
int main () {
int a;
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) cin >> k[i];
f[a] = true;
dfs(a,k[a],0);
if (ans == 0x7ffffff) ans = -1;
cout << ans << endl;
return 0;
}