求大佬帮我看看我的dfs哪里不对
查看原帖
求大佬帮我看看我的dfs哪里不对
441359
Fighting_For_211楼主2023/1/14 21:27
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=1106;
int n,a,b;
int k[N];
int d[N];

int bfs()
{
    queue<PII> q;
    q.push({a,0});
    d[a]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        for(int i=0;i<2;i++)
        {
            if(i==0)
            {
                int x=t.first+k[a];
                if(x<=b&&x>0&&d[x]==-1)
                {
                    d[x]=t.second+1;
                    q.push({x,d[x]});
                    if(x==b)
                    {
                        return d[b];
                    }
                }
            }
            else
            {
                int x=t.first-k[a];
                if(x<=b&&x>0&&d[x]==-1)
                {
                    d[x]=t.second+1;
                    q.push({x,d[x]});
                    if(x==b)
                    {
                        return d[b];
                    }
                }
            }
        }
    }
    return d[b];
}
int main()
{
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    cin>>k[i];

    memset(d,-1,sizeof(d));
    cout<<bfs()<<endl;
    system("pause");
    return 0;
}
2023/1/14 21:27
加载中...