DFS,只过了64%,坐牢俩小时了。求帮助。
查看原帖
DFS,只过了64%,坐牢俩小时了。求帮助。
994339
cyt_666楼主2024/11/24 11:58
#include <bits/stdc++.h>
// #define int long long
#define debuga(v, i) cout << #v << "[" << i << "]" << " = " << v[i] << '\n';
#define debug(x) cout << #x << " = " << x << '\n';
#define PI 3.1415926
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 211;

int n, a, b;
int d[N]; 
int res; // 答案
int st[N]; //记录是否走过
int ok; // 标记是否找到答案

void dfs(int k) { //k:当前楼层数
    if (ok) return ;
    if (k == b ) {
        cout << res << '\n';
        ok = 1;
        return ;
    }
    if (!st[k + d[k]] && k + d[k] >= 1 && k + d[k] <= n) {
        st[k + d[k]] = true;
        res ++;
        dfs(k + d[k]);
        res --;
    } 
    if (!st[k - d[k]] && k - d[k] >= 1 && k - d[k] <= n) {
        st[k - d[k]] = true;
        res ++;
        dfs(k - d[k]);
        res --;
    }
}

void solve() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i ++ ) {
        cin >> d[i];
    }
    dfs(a);
    if (!ok) cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
2024/11/24 11:58
加载中...