[Java] UVa 10009 All Roads Lead Where

題目連結

題意:
有若干城市，城市之間可能存在連線
每組測資先給定m，n
代表有 m 組程式間的連線
接著問 n 組，從某地到另一地可能的最短路徑

針對n行問題，每行輸出最短路徑的每個城市第一個字母

例如:
3 1
Aa Bb
Aa Cc
Cc Dd
Aa Dd
如上，m = 3，n = 1
Aa和Bb，Aa和Cc，還有Cc和Dd之間有連線
然後問Aa到Dd可以怎麼走

最短路徑為 Aa-Cc-Dd，輸出ACD

解法:
先透過HashMap建立連線
Key - Value 代表可以從城市 Key 到城市 Value

因為連線是雙向的
所以當input為A B時
要分別以A為Key加B Value，以B為Key加A Value

此外，因為一個城市可能可以同時連到多個其他城市
Value可以用ArrayList<> (等於一個key對應多個Value)

然後，實作上可以用BFS
先建立另一個HashMap(prev) 紀錄路徑
也就是以S為起點時，有沒有其他城市(Value)可以走到特定城市(Key)
所以一開始會輸入 prev.put(S, null); //S是起點

每次讀取S和D (出發和目的地)
先讀S，判斷可以走到哪些城市(也就是BFS的第一層search)
若城市的prev不存在(表示BFS還沒掃過)，就紀錄到prev

當掃到D，就透過prev回朔到S
可以建立一個反轉的字串，最後輸出即可

程式(Java):

	import java.util.*;
	public class Main {
	public static String bfs (HashMap<String, ArrayList<String>> list, String s, String d) {
	Queue<String> queue = new ArrayDeque<>();
	HashMap<String,String> prev = new HashMap<>();
	queue.offer(s);
	prev.put(s, null);
	while (!queue.isEmpty()) {
	String curr = queue.poll();
	if (curr.equals(d))
	break;
	else if (list.containsKey(curr)) { //find path from s to next
	for (String nei : list.get(curr)) {
	if (!prev.containsKey(nei)) {
	queue.offer(nei);
	prev.put(nei, curr); //d, s
	}
	}
	}
	}
	if (!prev.containsKey(d)) //never arrive
	return "";
	else {
	String ss = "";
	while (d != null) {
	ss = d.charAt(0) + ss;
	d = prev.getOrDefault(d, null); //trace
	}
	StringBuilder sb = new StringBuilder();
	return ss;
	}
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = Integer.parseInt(sc.nextLine());
	for (int k = 0; k < N; k++) {
	sc.nextLine();
	String[] st = sc.nextLine().split(" ");
	int m = Integer.parseInt(st[0]);
	int n = Integer.parseInt(st[1]);
	HashMap<String, ArrayList<String>>list = new HashMap<>();
	for (int i = 0; i < m; i++) {
	st = sc.nextLine().split(" ");
	String d1 = st[0];
	String d2 = st[1];
	//Build path
	if (!list.containsKey(d1))
	list.put(d1, new ArrayList<>());
	if (!list.containsKey(d2))
	list.put(d2, new ArrayList<>());
	list.get(d1).add(d2);
	list.get(d2).add(d1);
	}
	if (k > 0)
	System.out.println();
	for (int i = 0; i < n; i++) {
	st = sc.nextLine().split(" ");
	System.out.println(bfs(list, st[0], st[1]));
	}
	}
	}
	}

view raw UVa10009.java hosted with ❤ by GitHub