public class StationSched{/// <summary>/// 所有的站点信息/// </summary>List<StationInfo> stations = new List<StationInfo>();/// <summary>/// 线路信息/// </summary>List<ShipInfo> lines = new List<ShipInfo>();/// <summary>/// 构造函数,初始化站点和线路信息/// </summary>public StationSched(){stations.Add(new StationInfo() { Sid = 1, Lid = 1 });//0stations.Add(new StationInfo() { Sid = 2, Lid = 1 });//1stations.Add(new StationInfo() { Sid = 3, Lid = 1 });//2stations.Add(new StationInfo() { Sid = 4, Lid = 1 });//3stations.Add(new StationInfo() { Sid = 5, Lid = 1 });//4stations.Add(new StationInfo() { Sid = 6, Lid = 1 });//5stations.Add(new StationInfo() { Sid = 7, Lid = 1 });//6 stations.Add(new StationInfo() { Sid = 19, Lid = 2 });//7stations.Add(new StationInfo() { Sid = 18, Lid = 2 });stations.Add(new StationInfo() { Sid = 17, Lid = 2 });stations.Add(new StationInfo() { Sid = 3, Lid = 2 });stations.Add(new StationInfo() { Sid = 13, Lid = 2 });stations.Add(new StationInfo() { Sid = 16, Lid = 2 });stations.Add(new StationInfo() { Sid = 15, Lid = 3 });//13stations.Add(new StationInfo() { Sid = 14, Lid = 3 });stations.Add(new StationInfo() { Sid = 13, Lid = 3 });stations.Add(new StationInfo() { Sid = 12, Lid = 3 });stations.Add(new StationInfo() { Sid = 11, Lid = 3 });stations.Add(new StationInfo() { Sid = 5, Lid = 3 });stations.Add(new StationInfo() { Sid = 10, Lid = 3 });stations.Add(new StationInfo() { Sid = 9, Lid = 3 });stations.Add(new StationInfo() { Sid = 8, Lid = 3 });for (int i = 0; i < 6; i++){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });}for (int i = 6; i > 0; i--){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });}for (int i = 7; i < 12; i++){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });}for (int i = 12; i > 7; i--){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });}for (int i = 13; i < 21; i++){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });}for (int i = 21; i > 13; i--){lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });}}/// <summary>/// 获取sid站点可以到达的站点信息,去除已经计算过的preid站点/// </summary>/// <param name="preid"></param>/// <param name="sid"></param>/// <returns></returns>public List<StationInfo> GetNext(int preid, int sid){List<StationInfo> list = new List<StationInfo>();foreach (var item in lines){if (item.Curr.Sid == sid && item.Next.Sid != preid) list.Add(item.Next);}return list;}/// <summary>/// 获取线路信息/// </summary>/// <param name="s">起始站点编号</param>/// <param name="e">结束站点编号</param>/// <returns></returns>public List<string> GetResult(int s, int e){List<List<int>> temp = GetLine(s, e);List<string> result = new List<string>();List<List<int>> line = new List<List<int>>();foreach (var item in temp){if (item.Count > 0 && item[item.Count - 1] == e)line.Add(item);}string src = "";int currLine = -1;foreach (var item in line){currLine = GetLineNumber(item[0], item[1]);src += "从[" + currLine + "号线]的[" + item[0] + "]上车";for (int i = 1; i < item.Count; i++){if (i == item.Count - 1){src += ",在[" + item[i] + "]站点下车。";result.Add(src);src = "";break;}int tempLine = GetLineNumber(item[i], item[i + 1]);if (tempLine != currLine){currLine = tempLine;src += ",在[" + item[i] + "]站点换乘[" + currLine + "号线]";}}}return result;}/// <summary>/// 根据相邻的两个点取当前的线路/// </summary>/// <param name="s"></param>/// <param name="e"></param>/// <returns></returns>private int GetLineNumber(int l, int r){foreach (var item in lines){if ((item.Curr.Sid == l && item.Next.Sid == r) || (item.Curr.Sid == r && item.Next.Sid == l))return item.Next.Lid;}return -1;}/// <summary>/// 获取线路的ID集合/// </summary>/// <param name="s">起始站点编号</param>/// <param name="e">结束站点编号</param>/// <returns></returns>private List<List<int>> GetLine(int s, int e){List<List<int>> result = new List<List<int>>();List<int> curr = new List<int>();curr.Add(s);result.Add(curr);int currLine = 0;int preSid = s;int currSid = s;while (true){if (currLine >= result.Count) return result;currSid = result[currLine][result[currLine].Count - 1];if (currSid == e){currLine += 1;continue;}if (result[currLine].Count > 1)preSid = result[currLine][result[currLine].Count - 2];if (currSid <= 0){currLine += 1;continue;}List<StationInfo> temp = GetNext(preSid, currSid);if (temp.Count == 0){//某条线路到头currLine += 1;}else if (temp.Count == 1){//不需要换乘继续前进result[currLine].Add(temp[0].Sid);}else{//需要换乘了。for (int i = 1; i < temp.Count; i++){if (!result[currLine].Contains(temp[i].Sid)){//防止死循环,过滤掉已经计算过的站点。result.Add(result[currLine].GetRange(0, result[currLine].Count));result[result.Count - 1].Add(temp[i].Sid);}}result[currLine].Add(temp[0].Sid);}}}}/// <summary>/// 站点信息/// </summary>public class StationInfo{public int Lid { get; set; }public int Sid { get; set; }public override string ToString(){return "Sid:" + Sid + "--Lid:" + Lid;}}/// <summary>/// 关系信息/// </summary>public class ShipInfo{public StationInfo Curr { get; set; }public StationInfo Next { get; set; }public override string ToString(){return "Curr:" + Curr.Sid + "--Next:" + Next.Sid;}}
调用
StationSched ss = new StationSched();List<string> lines = ss.GetResult(16, 4);for (int i = 0; i < lines.Count; i++){Console.WriteLine(lines[i]);}Console.ReadLine();
输出结果
本文转自:http://www.cnblogs.com/danyueweb/p/4174211.html