蒟蒻求救!!DFS 6tle优化不动了
查看原帖
蒟蒻求救!!DFS 6tle优化不动了
1179393
Noldo楼主2024/3/17 10:55
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 205;
int n, a, b;
int k[N];
int ans = 1e9;
bool vis[N];
void dfs(int x, int cnt) {
    if (x == b) { ans = min(ans, cnt); return; } 
    if (cnt+1 >= ans)return;//按钮次数大于当前最优时return
    if (x<1 || x>n)return;//越界return
    if (vis[x])return;//访问过return
    if (k[x] == 0)return;//电梯不动return
    
    vis[x] = 1;
    dfs(x + k[x], cnt+1);
    vis[x] = 0;
    
    vis[x] = 1;
    dfs(x - k[x], cnt+1);
    vis[x] = 0;
}
int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> k[i];
    }
    dfs(a, 0);
    if (ans == 1e9)cout << "-1" << endl;
    else cout << ans << endl;
    return 0;
}
2024/3/17 10:55
加载中...