送外卖 DFS迭代

送外卖

输入样例：

7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0

输出样例：

abbbb

代码：

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define bug(x) cerr<<#x<<" : "<<x<<endl;
typedef long long ll;

const int N=1000010;
char ans[N];
int flag=0,n;
int a[N],b[N],vis[N],st[N];//判断是否走过


bool dfs(int u,int step)//判断能否在step步到达U点。
{
    if(u<1||u>n) return false;
    if(u==n) {
        ans[step]='\0';
        return true;//到n结束
    }
    if(vis[u]){
        st[u]=1;//如果反复到那个点，死循环，
        return false;
    } 
    vis[u]=1;
    //走A
    if(dfs(u+a[u],step+1)){
        ans[step]='a';
        if(st[u]) flag=1;
        return true;
    } 
    //走B 
    if(dfs(u+b[u],step+1)){
        ans[step]='b';
        if(st[u]) flag=1;
        return true;
    }
    return false;
} 


int main(){
    //int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    if(dfs(1,0)){
        if(flag) puts("Infinity!");
        else puts(ans);
    }
    else puts("No solution!");
    return 0;
}