package com.patrick.bishi;
 
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;
 
/**
 * 獲取兩條地鐵線上兩點間的最短站點數(shù)
 * 
 * @author patrick
 * 
 */
public class SubTrain {
	private static LinkedList<String> subA = new LinkedList<String>();
	private static LinkedList<String> subB = new LinkedList<String>();
 
	public static void main(String[] args) {
		String sa[] = { "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9",
				"T1", "A10", "A11", "A12", "A13", "T2", "A14", "A15", "A16",
				"A17", "A18" };
		String sb[] = { "B1", "B2", "B3", "B4", "B5", "T1", "B6", "B7", "B8",
				"B9", "B10", "T2", "B11", "B12", "B13", "B14", "B15" };
		Set<String> plots = new HashSet<String>();
		for (String t : sa) {
			plots.add(t);
			subA.add(t);
		}
		for (String t : sb) {
			plots.add(t);
			subB.add(t);
		}
		Scanner in = new Scanner(System.in);
		String input = in.nextLine();
		String trail[] = input.split("\\s");
		String src = trail[0];
		String dst = trail[1];
		if (!plots.contains(src) || !plots.contains(dst)) {
			System.err.println("no these plot!");
			return;
		}
		int len = getDistance(src, dst);
		System.out.printf("The shortest distance between %s and %s is %d", src,
				dst, len);
	}
 
	// 經(jīng)過兩個換乘站點后的距離
	public static int getDist(String src, String dst) {
		int len = 0;
		int at1t2 = getDistOne("T1", "T2");
		int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1") + 1;
		int a = 0;
		if (src.equals("T1")) {
			a = getDistOne(dst, "T2");
			len = a + bt1t2 - 1;// two part must more 1
		} else if (src.equals("T2")) {
			a = getDistOne(dst, "T1");
			len = a + bt1t2 - 1;
		} else if (dst.equals("T1")) {
			a = getDistOne(src, "T2");
			len = a + at1t2 - 1;
		} else if (dst.equals("T2")) {
			a = getDistOne(src, "T1");
			len = a + at1t2 - 1;
		}
		return len;
	}
 
	// 獲得一個鏈表上的兩個元素的最短距離
	private static int getDistOne(String src, String dst) {
		int aPre, aBack, aLen, len, aPos, bPos;
		aPre = aBack = aLen = len = 0;
		aLen = subA.size();
		if ("T1".equals(src) && "T2".equals(dst)) {
			int a = subA.indexOf("T1");
			int b = subA.indexOf("T2");
			int at1t2 = (b - a) > (a + aLen - b) ? (a + aLen - b) : (b - a);
			int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1");
			len = at1t2 > bt1t2 ? bt1t2 : at1t2;
		} else if (subA.contains(src) && subA.contains(dst)) {
			aPos = subA.indexOf(src);
			bPos = subA.indexOf(dst);
			if (aPos > bPos) {
				aBack = aPos - bPos;
				aPre = aLen - aPos + bPos;
				len = aBack > aPre ? aPre : aBack;
			} else {
				aPre = bPos - aPos;
				aBack = aLen - bPos + aPos;
				len = aBack > aPre ? aPre : aBack;
			}
		} else if (subB.contains(src) && subB.contains(dst)) {
			aPos = subB.indexOf(src);
			bPos = subB.indexOf(dst);
			len = aPos > bPos ? (aPos - bPos) : (bPos - aPos);
		} else {
			System.err.println("Wrong!");
		}
		return len + 1;
	}
 
	public static int getDistance(String src, String dst) {
		int aPre, aBack, len, aLen;
		aPre = aBack = len = aLen = 0;
		aLen = subA.size();
		int a = subA.indexOf("T1");
		int b = subA.indexOf("T2");
		int at1t2 = (b - a) > (a + aLen - b) ? (a + aLen - b) : (b - a);
		int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1");
		if ((subA.contains(src) && subA.contains(dst))
				|| (subB.contains(src) && subB.contains(dst))) {
			len = getDistOne(src, dst);
			if (src.equals("T1") || src.equals("T2") || dst.equals("T1")
					|| dst.equals("T2")) {
				int t = getDist(src, dst);
				len = len > t ? t : len;
			}
		} else {
			int at1 = getDist(src, "T1");
			int at2 = getDist(src, "T2");
			int bt1 = getDist(dst, "T1");
			int bt2 = getDist(dst, "T2");
			aPre = at1 + bt1 - 1;
			aBack = at2 + bt2 - 1;
			len = aBack > aPre ? aPre : aBack;
			aPre = at1t2 + at1 + bt2 - 2;
			aBack = bt1t2 + at2 + bt1 - 2;
			int tmp = aBack > aPre ? aPre : aBack;
			len = len > tmp ? tmp : len;
		}
		return len;
	}
}

通用乘地鐵方案的實現(xiàn)（最短距離利用Dijkstra算法）：
package com.patrick.bishi;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
/**
 * 地鐵中任意兩點的最有路徑
 * 
 * @author patrick
 * 
 */
public class SubTrainMap<T> {
	protected int[][] subTrainMatrix; // 圖的鄰接矩陣，用二維數(shù)組表示
	private static final int MAX_WEIGHT = 99; // 設置最大權值，設置成常量
	private int[] dist;
	private List<T> vertex;// 按順序保存頂點s
	private List<Edge> edges;
 
	public int[][] getSubTrainMatrix() {
		return subTrainMatrix;
	}
 
	public void setVertex(List<T> vertices) {
		this.vertex = vertices;
	}
 
	public List<T> getVertex() {
		return vertex;
	}
 
	public List<Edge> getEdges() {
		return edges;
	}
 
	public int getVertexSize() {
		return this.vertex.size();
	}
 
	public int vertexCount() {
		return subTrainMatrix.length;
	}
 
	@Override
	public String toString() {
		String str = "鄰接矩陣：\n";
		int n = subTrainMatrix.length;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				str += this.subTrainMatrix[i][j] == MAX_WEIGHT ? " $" : " "
						+ this.subTrainMatrix[i][j];
			str += "\n";
		}
		return str;
	}
 
	public SubTrainMap(int size) {
		this.vertex = new ArrayList<T>();
		this.subTrainMatrix = new int[size][size];
		this.dist = new int[size];
		for (int i = 0; i < size; i++) { // 初始化鄰接矩陣
			for (int j = 0; j < size; j++) {
				this.subTrainMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT;// 無向圖
			}
		}
	}
 
	public SubTrainMap(List<T> vertices) {
		this.vertex = vertices;
		int size = getVertexSize();
		this.subTrainMatrix = new int[size][size];
		this.dist = new int[size];
		for (int i = 0; i < size; i++) { // 初始化鄰接矩陣
			for (int j = 0; j < size; j++) {
				this.subTrainMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT;
			}
		}
	}
 
	/**
	 * 獲得頂點在數(shù)組中的位置
	 * 
	 * @param s
	 * @return
	 */
	public int getPosInvertex(T s) {
		return vertex.indexOf(s);
	}
 
	public int getWeight(T start, T stop) {
		int i = getPosInvertex(start);
		int j = getPosInvertex(stop);
		return this.subTrainMatrix[i][j];
	} // 返<vi,vj>邊的權值
 
	public void insertEdge(T start, T stop, int weight) { // 插入一條邊
		int n = subTrainMatrix.length;
		int i = getPosInvertex(start);
		int j = getPosInvertex(stop);
		if (i >= 0 && i < n && j >= 0 && j < n
				&& this.subTrainMatrix[i][j] == MAX_WEIGHT && i != j) {
			this.subTrainMatrix[i][j] = weight;
			this.subTrainMatrix[j][i] = weight;
		}
	}
 
	public void addEdge(T start, T dest, int weight) {
		this.insertEdge(start, dest, weight);
	}
 
	public void removeEdge(String start, String stop) { // 刪除一條邊
		int i = vertex.indexOf(start);
		int j = vertex.indexOf(stop);
		if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount()
				&& i != j)
			this.subTrainMatrix[i][j] = MAX_WEIGHT;
	}
 
	@SuppressWarnings("unused")
	private static void newGraph() {
		List<String> vertices = new ArrayList<String>();
		vertices.add("A");
		vertices.add("B");
		vertices.add("C");
		vertices.add("D");
		vertices.add("E");
 
		graph = new SubTrainMap<String>(vertices);
 
		graph.addEdge("A", "B", 5);
		graph.addEdge("A", "D", 2);
		graph.addEdge("B", "C", 7);
		graph.addEdge("B", "D", 6);
		graph.addEdge("C", "D", 8);
		graph.addEdge("C", "E", 3);
		graph.addEdge("D", "E", 9);
 
	}
 
	private static SubTrainMap<String> graph;
 
	/** 打印頂點之間的距離 */
	public void printL(int[][] a) {
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				System.out.printf("%4d", a[i][j]);
			}
			System.out.println();
		}
	}
 
	public static void main(String[] args) {
		// newGraph();
		String sa[] = { "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9",
				"T1", "A10", "A11", "A12", "A13", "T2", "A14", "A15", "A16",
				"A17", "A18" };
		String sb[] = { "B1", "B2", "B3", "B4", "B5", "T1", "B6", "B7", "B8",
				"B9", "B10", "T2", "B11", "B12", "B13", "B14", "B15" };
		List<String> vertices = new ArrayList<String>();
		for (String t : sa) {
			if (!vertices.contains(t)) {
				vertices.add(t);
			}
		}
		for (String t : sb) {
			if (!vertices.contains(t)) {
				vertices.add(t);
			}
		}
		graph = new SubTrainMap<String>(vertices);
		for (int i = 0; i < sa.length - 1; i++)
			graph.addEdge(sa[i], sa[i + 1], 1);
		graph.addEdge(sa[0], sa[sa.length - 1], 1);
		for (int i = 0; i < sb.length - 1; i++)
			graph.addEdge(sb[i], sb[i + 1], 1);
 
		Scanner in = new Scanner(System.in);
		System.out.println("請輸入起始站點：");
		String start = in.nextLine().trim();
		System.out.println("請輸入目標站點：");
		String stop = in.nextLine().trim();
		if (!graph.vertex.contains(start) || !graph.vertex.contains(stop)) {
			System.out.println("地圖中不包含該站點！");
			return;
		}
		int len = graph.find(start, stop) + 1;// 包含自身站點
		System.out.println(start + " -> " + stop + " 經(jīng)過的站點數(shù)為： " + len);
	}
 
	public int find(T start, T stop) {
		int startPos = getPosInvertex(start);
		int stopPos = getPosInvertex(stop);
		if (startPos < 0 || startPos > getVertexSize())
			return MAX_WEIGHT;
		String[] path = dijkstra(startPos);
		System.out.println("從" + start + "出發(fā)到" + stop + "的最短路徑為："
				+ path[stopPos]);
		return dist[stopPos];
	}
 
	// 單元最短路徑問題的Dijkstra算法
	private String[] dijkstra(int vertex) {
		int n = dist.length - 1;
		String[] path = new String[n + 1]; // 存放從start到其他各點的最短路徑的字符串表示
		for (int i = 0; i <= n; i++)
			path[i] = new String(this.vertex.get(vertex) + "-->"
					+ this.vertex.get(i));
 
		boolean[] visited = new boolean[n + 1];
		// 初始化
		for (int i = 0; i <= n; i++) {
			dist[i] = subTrainMatrix[vertex][i];// 到各個頂點的距離，根據(jù)頂點v的數(shù)組初始化
			visited[i] = false;// 初始化訪問過的節(jié)點，當然都沒有訪問過
		}
 
		dist[vertex] = 0;
		visited[vertex] = true;
 
		for (int i = 1; i <= n; i++) {// 將所有的節(jié)點都訪問到
			int temp = MAX_WEIGHT;
			int visiting = vertex;
			for (int j = 0; j <= n; j++) {
				if ((!visited[j]) && (dist[j] < temp)) {
					temp = dist[j];
					visiting = j;
				}
			}
			visited[visiting] = true; // 將距離最近的節(jié)點加入已訪問列表中
			for (int j = 0; j <= n; j++) {// 重新計算其他節(jié)點到指定頂點的距離
				if (visited[j]) {
					continue;
				}
				int newdist = dist[visiting] + subTrainMatrix[visiting][j];// 新路徑長度，經(jīng)過visiting節(jié)點的路徑
				if (newdist < dist[j]) {
					// dist[j] 變短
					dist[j] = newdist;
					path[j] = path[visiting] + "-->" + this.vertex.get(j);
				}
			}// update all new distance
 
		}// visite all nodes
			// for (int i = 0; i <= n; i++)
		// System.out.println("從" + vertex + "出發(fā)到" + i + "的最短路徑為：" + path[i]);
		// System.out.println("=====================================");
		return path;
	}
 
	/**
	 * 圖的邊
	 * 
	 * @author patrick
	 * 
	 */
	class Edge {
		private T start, dest;
		private int weight;
 
		public Edge() {
		}
 
		public Edge(T start, T dest, int weight) {
			this.start = start;
			this.dest = dest;
			this.weight = weight;
		}
 
		public String toString() {
			return "(" + start + "," + dest + "," + weight + ")";
		}
 
	}
 
}