java算法

Question

题目如下：
The number of different path from C to C with duration of less than 30. In the sample data, the paths are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

题目意思大致是求出 C to C 在 长度在不超过30范围内共有过少条路径？

Answer 1

BSF:

private static class Pair{
    char c;
    int duration;

    public Pair(char c, int duration) {
        this.c = c;
        this.duration = duration;
    }
}

public int search(String[] input){
    Map<Character, Set<Pair>> map = new HashMap<>();
    for(String s: input){
        char c1 = s.charAt(0), c2 = s.charAt(1);
        int duration = s.charAt(2) - '0';
        if(!map.containsKey(c1))
            map.put(c1, new HashSet<>());
        map.get(c1).add(new Pair(c2, duration));
    }

    int count = 0;
    Queue<Pair> q = new LinkedList<Pair>();
    q.offer(new Pair('C', 0));
    while(!q.isEmpty()){
        int size = q.size();
        while(size-- > 0){
            Pair cur = q.poll();
            for(Pair p: map.get(cur.c)){
                if(cur.duration + p.duration >= 30)
                    continue;
                if(p.c == 'C')
                    count++;
                q.offer(new Pair(p.c, cur.duration + p.duration));
            }
        }
    }
    return count;
}

@Test
public void test(){
    assertEquals(7, search(new String[]{"AB5", "BC4", "CD8", "DC8", "DE6", 
            "AD5", "CE2", "EB3", "AE7"}));
}

Answer 2

题目没有给出数据范围，如果数据比较小的话，在每个点上挂一张表，表示从C到该点有哪些路径长度可行，然后从C开始做一遍BFS即可，最后统计C点上表的大小即可。如果数据比较大可以考虑Tarjan缩环啥的……