大佬们,BFS悬关求调
查看原帖
大佬们,BFS悬关求调
881317
spessert楼主2024/3/28 10:03

前面6个RE了,后边的基本都是WA

#include <iostream>
#include <queue>
using namespace std;
int N,A,B;
int num[2005];
struct cal {
    int x,d;  //到达层数x和第几次运算d
} ca;
queue<cal> qu;
int flag=0;
void BFS() {
    ca.x=A;
    ca.d=0;
    qu.push(ca);
    int i=1;
    int dep=1;
    while(!qu.empty()) {
        int len=qu.size();
        while(len) {
            //加
            ca.x=ca.x+num[i]-1;
            ca.d=dep;
            if(ca.x>=1) {
                qu.push(ca);
            }
            if(ca.x==B) {
                cout << ca.d;
                flag=1;
                return ;
            }
            //减
            ca.x=ca.x-num[i]+1;
            ca.d=dep;
            if(ca.x>=1) {
                qu.push(ca);
            }
            if(ca.x==B) {
                cout << ca.d;
                flag=1;
                return ;
            }
            i++;
            qu.pop();
            len--;
        }
        dep++;
    }
}

int main() {
    cin>>N>>A>>B;
    for(int i = 1; i<=N; i++) {
        cin >> num[i];
    }
    BFS();
    if(flag==0)
    {
        cout << -1;
    }
    return 0;
}
2024/3/28 10:03
加载中...