求解为何这样dfs不行
查看原帖
求解为何这样dfs不行
823227
lightmon楼主2023/1/2 21:42

6, 7, 9, 10, 11WA, 1TLE

#include <iostream>

using namespace std;

const int N = 210;
int k[N];
int n, a, b;
int v[N];
int cnt = 0, ans = 0x3f3f3f3f;
int flag = 0;

void search(int u){
    if(cnt >= ans){
        return;
    }
    if(u == b){
        flag = 1;
        ans = min(ans, cnt);
        cnt = 0;
        return;
    }
    if(u + k[u] <= n && !v[u + k[u]]) {
        v[u + k[u]] = 1;
        cnt++;
        search(u + k[u]);
        v[u + k[u]] = 0;
        cnt--;
    }
    if(u - k[u] >= 1 && !v[u - k[u]]) {
        v[u - k[u]] = 1;
        cnt++;
        search(u - k[u]);
        v[u - k[u]] = 0;
        cnt--;
    }
}

int main(){
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) cin >> k[i];
    v[a] = 1;
    search(a);
    if(flag == 1) cout << ans;
    else cout << -1;
    return 0;
}
2023/1/2 21:42
加载中...