为什么迭代加深dfs也会被卡?
查看原帖
为什么迭代加深dfs也会被卡?
537934
litjohn楼主2024/3/31 14:56

rt。

#include <bits/stdc++.h>

using namespace std;
long long n, a, b, k[205], maxdepth;
bool vis[205];

void iddfs(long long f, long long depth) {
    if (depth > maxdepth) {
        return;
    } else if (f == b) {
        cout << depth;
        exit(0);
    } else {
        vis[f] = true;
        if (f - k[f] > 0 && f - k[f] <= n && !vis[f - k[f]]) {
            iddfs(f - k[f], depth + 1);
        }
        if (f + k[f] > 0 && f + k[f] <= n && !vis[f + k[f]]) {
            iddfs(f + k[f], depth + 1);
        }
        vis[f] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> a >> b;
    if (a == b) {
        cout << 0;
        exit(0);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
    }
    for (maxdepth = 1; maxdepth <= n; ++maxdepth) {
        iddfs(a, 0);
    }
    cout << -1;
    return 0;
}
2024/3/31 14:56
加载中...