疯狂游戏3.1第三题解法
大家帮忙看看有什么问题？还有没有别的解法，因为是考试完静下来才做出来的，不知道对不对。。也没考虑有向图成环的问题。
第二题直接print("1")就能过50+%，还有老哥用random()%2过了60+的，真神了。。。
public class test202031 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String[] split = s.split("\\|");
// list为所需要匹配的开始节点
char[] c = split[1].toCharArray();
List<String> list = new ArrayList<String>();
for (int i = 0; i < c.length; i++) {
if (c[i] <= '9' && c[i] >= '0') {
list.add(c[i] + "");
}
}
char[] d = split[0].toCharArray();
List<String> list2 = new ArrayList<String>();
for (int i = 0; i < d.length; i++) {
if (d[i] <= '9' && d[i] >= '0') {
list2.add(d[i] + "");
}
}
// map为有向图的指向
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < list2.size(); i = i + 2) {
if (map.get(list2.get(i)) == null) {
List<String> list3 = new ArrayList<String>();
int m = i + 1;
list3.add(list2.get(m));
map.put(list2.get(i), list3);
} else {
List<String> list3 = map.get(list2.get(i));
int m = i + 1;
list3.add(list2.get(m));
map.put(list2.get(i), list3);
}
}
System.out.println(map.toString());
//end为匹配的最终节点
String end = split[2];
for (String s1 : list) {
getResult(map, s1, end, new ArrayList<String>());
}
System.out.println(set.toString());
}
public static Set<String> set = new HashSet<>();
//递归思路就是先从起始点开始的点加到list，再对list中的点进行下一步的递归，如果最终匹配到最终点了就把整个路径加到set中
public static void getResult(Map<String, List<String>> map, String start, String end, List<String> list) {
if (start.equals(end)) {
list.add(end);
set.addAll(list);
return;
}
list.add(start);
List<String> list1 = map.get(start);
if (list1 != null) {
for (String s : list1) {
getResult(map, s, end, list);
}
}
}
}
