送外卖（DFS）

送外卖（DFS）

题目传送门

题目描述

n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择：
1) 选择a：向前 a[i] 个小区。
2) 选择b：向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。
• 当没有合法的选择序列时，输出 “No solution!”。
• 当字典序最小的字符串无限长时，输出 “Infinity!”。
• 否则，输出这个选择字符串。

字典序定义如下：串s和串t，如果串 s 字典序比串 t 小，则
• 存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中，空字符 < ‘a’ < ‘b’。

输入描述:

输入有 3 行。第一行输入一个整数 n (1 ≤ n ≤ 10^5)。第二行输入 n 个整数，分别表示 a[i] 。第三行输入 n 个整数，分别表示 b[i] 。−n ≤ a[i], b[i] ≤ n

输出描述:

输出一行字符串表示答案。

示例1

输入

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

输出

abbbb

分析：一个相对比较简单的DFS题，题目要求最小字典序列，使用DFS非常适合本题。每次搜索时在一个小区只有A，B两种选择，分别递归两种选择，并用一个vis数组记录访问点用来防止死循环，并用st数组记录循环点位置，在函数执行完返回的时候以便能找到这个点标记flag，最后递归完成后输出对应结果即可。

#include<cstdio>
#include<string>
#define N 10005
using namespace std;
int a[N],b[N],vis[N],st[N],n,flag;
char str[N];
bool dfs(int u,int step){if(u<1||u>n) return false; //若这个选择越界，则No solutionif(u==n){ str[step+1]=''; return true;}//若访问到n点，则输出字典序if(vis[u]){   st[u]=1; return false;}//若该点之前访问过，则标记vis[u]=1;//对新访问的点进行标记if(dfs(u+a[u],step+1)){ //对这个点先进行A选择str[step]='a';    //若可行，则在字典序中标记此点if(st[u]) flag=1; //若在尝试过程中遇到重复，标记flagreturn true;}if(dfs(u+b[u],step+1)){ //对这个点先进行B选择str[step]='b';if(st[u]) flag=1;return true;}return false;
}
int main(){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]);bool ans = dfs(1,0);if(ans){if(flag)    puts("Infinity!");else puts(str);}else puts("No solution!");
}
/*
7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0
*/