【DFS爆搜+判环】送外卖

蔚落 2024-03-24 09:30 65阅读 0赞

这道题加深了我对DFS中vis数组的理解

一般来讲，在回溯的过程中，vis是重新置0的

但是这道题为了判环，在回溯的过程中没有把vis数组置0，而是去维护了结点的访问次数，如果一个结点的访问次数>1，说明包含这个结点的路径一定存在环

如果存在环，就说明它的答案的长度是无穷大的

怎么去判环：在得到路径之后去沿着路径走一遍，如果出现一个在环里的结点，说明该路径存在环

[1006-送外卖\_2021秋季算法入门班第六章习题：搜索与搜索剪枝 (nowcoder.com)][1006-_2021_ _nowcoder.com]

题意：

![de5d85cd7be44cb4a56c94c0a373f2a7.png][]

思路：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    priority_queue<string,vector<string>,greater<string> > q;
    string ans;
    int n,ok=0;
    int a[mxn],b[mxn],c[mxn],vis[mxn];
    bool check(int x){
        return x>=0&&x<=n-1;
    }
    void dfs(int x){
        if(ok) return;
        if(vis[x]){
            vis[x]++;
            return;
        }else vis[x]++;
        if(x==n-1){
            ok=1;
            q.push(ans);
            return;
        }
        int v1=x+a[x];
        if(check(v1)){
            ans.push_back('a');
            dfs(v1);
            ans.pop_back();
        }
        int v2=x+b[x];
        if(check(v2)){
            ans.push_back('b');
            dfs(v2);
            ans.pop_back();
        }
    }
    void solve(){
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        for(int i=0;i<n;i++) cin>>b[i];
        dfs(0);
        if(q.empty()) cout<<"No solution!"<<'\n';
        else{
            ans=q.top();
            int p=0,ok2=0;
            for(int i=0;i<ans.size();i++){
                if(vis[p]>1) ok2=1;
                if(ans[i]=='a') p+=a[p];
                else p+=b[p];
            }
            if(ok2) cout<<"Infinity!"<<'\n';
            else cout<<ans<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1006-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/23156/1006
[de5d85cd7be44cb4a56c94c0a373f2a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/59b52ac56d5b4cceb65377eac01ceb71.png