首页 > 代码库 > 计算地铁换乘--计算出所有的线路
计算地铁换乘--计算出所有的线路
地铁测试线路图
源码
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 });//0 stations.Add(new StationInfo() { Sid = 2, Lid = 1 });//1 stations.Add(new StationInfo() { Sid = 3, Lid = 1 });//2 stations.Add(new StationInfo() { Sid = 4, Lid = 1 });//3 stations.Add(new StationInfo() { Sid = 5, Lid = 1 });//4 stations.Add(new StationInfo() { Sid = 6, Lid = 1 });//5 stations.Add(new StationInfo() { Sid = 7, Lid = 1 });//6 stations.Add(new StationInfo() { Sid = 19, Lid = 2 });//7 stations.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 });//13 stations.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 = http://www.mamicode.com/""; 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();
输出结果
计算地铁换乘--计算出所有的线路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。