广搜6分/深搜12分求助(MLE)
查看原帖
广搜6分/深搜12分求助(MLE)
1047598
GZXUEXUE楼主2024/8/17 19:44

广搜代码(#7 AC,其余MLE):

# include <iostream>
# include <queue>
using namespace std;
int n,a,b,k[250];
struct node{
    int x,step;
};int bfs(){
    queue<node> q;
    q.push({a,0});
    while (!q.empty()){
        node f = q.front();
        if (f.x == b) return f.step;
        if (f.x + k[f.x] <= n) q.push({f.x+k[f.x],f.step+1});
        if (f.x - k[f.x] > 0) q.push({f.x-k[f.x],f.step+1});
    }return -1;
}int main(){
    cin >> n >> a >> b;
    for (int i = 0;i < n;i++) cin >> k[i];
    cout << bfs();
    return 0;
}

深搜代码(#7、#10 AC,其余MLE):

# include <iostream>
# include <queue>
using namespace std;
int n,a,b,k[250];
int dfs(int x,int step){
    if (x < 1 || x > n) return -1;
    if (x == b) return step;
    int Min = 0x3f3f3f3f;
    int ans1 = dfs(x+k[x],step+1),ans2 = dfs(x-k[x],step+1);
    if (ans1 != -1) Min = min(Min,ans1);
    if (ans2 != -1) Min = min(Min,ans2);
    if (Min != 0x3f3f3f3f) return Min;
    return -1;
}int main(){
    cin >> n >> a >> b;
    for (int i = 0;i < n;i++) cin >> k[i];
    cout << dfs(a,0);
    return 0;
}

求助各位大佬qwq

2024/8/17 19:44
加载中...