题解 | #送外卖#

这道题其实考察的知识点不难，甚至可以说是简单，就dfs完事.

但是坑就坑在这个"Infinity!"上,因为题干没有给出合适的测试用例,导致我理解错了题意！

不知道你们对输出"Infinity!"的条件的理解是什么,我最开始理解成只需要满足"最小字典序"和"无限长(即有环存在)"就应该打印出"Infinity!",而且题干字面也是这个意思(吐槽:真的很容易误导人!)，但代码提交后却未通过.

然后我看了其他人的代码,发现和我写的基本一样,但对于"Infinity!"，却存在第三个条件：最终能达到n-1这个位置。也就是说，想要输出"Infinity!"，必须字典序最小且无限长且最终能达到n-1这个位置。

比如: "aaabb"是一条能到达n-1的路径，"aaa(ab)bb"也是一条到达n-1的路径，两者不同的是括号里的路径是一个环,那么这个路径的通式可以写作:"aaa[(ab) * n]bb"，其中n >= 0。那么此时就应该输出"Infinity!"，因为n越大，字典序越小，n可以是无穷大的整数。

所以代码如下：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    
    private boolean isInfinity = false;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n], b = new int[n];
        String[] strs = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            a[i] = Integer.parseInt(strs[i]);
        }
        strs = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            b[i] = Integer.parseInt(strs[i]);
        }
        StringBuilder sb = new StringBuilder();
        boolean[] visited = new boolean[n];
        boolean[] flag = new boolean[n];
        Main m = new Main();
        
        System.out.println(m.search(a, b, sb, 0, visited, flag) ? (m.isInfinity ? "Infinity!" : sb.toString()) : "No solution!");
    }
    private boolean search(int[] a, int[] b, StringBuilder sb, int begin, boolean[] visited, boolean[] flag){
        if(begin < 0 || begin >= a.length || visited[begin]){
            if(begin >= 0 && begin < a.length){
                flag[begin] = true;
            }
            return false;
        }
        if(begin == a.length - 1){
            return true;
        }
        visited[begin] = true;
        sb.append('a');
        if(search(a, b, sb, begin + a[begin], visited, flag)){
            if(flag[begin])
                isInfinity = true;
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append('b');
        if(search(a, b, sb, begin + b[begin], visited, flag)){
            if(flag[begin])
                isInfinity = true;
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);
        return false;
    }
}