connectivechart.cs

csharp开发

using System;
using System.Collections;

namespace TrainRoute
{
	/// <summary>
	/// Class1 的摘要说明。
	/// </summary>
	class ConnectiveChart
	{
		const int MAX = 10000;
		static int cityNumber;			//输入的城市数目
		static string inputString;		//输入的连通图信息，必须严格按照“始点+终点+权值+空格”的格式输入
		static int routeNumber;			//连通图中直接可达的路径数目
		struct Route
		{
			public char origination;
			public char termination;
			public int weight;
		}
		static Route[] routeArray;		//结构数组，数组中的每一个值表示每一条直接可达的路径的信息
		static int[,] Matrix;

		static void ConvertStrToArray()
		{//将输入的连通图信息（字符串格式的）转化为结构数组
			routeNumber = (inputString.Length+2)/4;
			routeArray = new Route[routeNumber];
			for(int index = 0; index < routeNumber; index++)
			{
				routeArray[index].origination = inputString[4*index];
				routeArray[index].termination = inputString[4*index+1];
				//routeArray[index].weight = int.Parse(Convert.ToString(inputString[4*index+2]));
				routeArray[index].weight = (int)Char.GetNumericValue(inputString[4*index+2]);
			}
		}

		static void ConvertArrayToMatrix()
		{
			int i, j;
			int index;
			Matrix = new int[cityNumber, cityNumber];
			for(i = 0; i < cityNumber; i++)
				for(j = 0;j < cityNumber; j++)
					Matrix[i, j] = MAX;
 
			for(index = 0; index < routeNumber; index++)
				Matrix[routeArray[index].origination-'A',routeArray[index].termination-'A'] = routeArray[index].weight;
		}

		static int Distance(string routeString)
		{//求routeString所给出的路线的距离
			char[] charArray = routeString.ToCharArray();
			int distance = 0;
			int i;
			int j;

			for(i = 0; i < charArray.Length-1; i++)
			{
				for(j = 0; j < routeNumber; j++)
				{
					if((routeArray[j].origination == charArray[i])&&(routeArray[j].termination == charArray[i+1]))
					{
						distance += routeArray[j].weight;
						break;
					}
				}
				if(j == routeNumber)
					distance = 0;
			}
			return distance;
		}

		static int RouteCount(char origination, char termination, int stopNumber)
		{//求从origination出发到termination结束，停顿stopNumber次的路线数目
			Queue routeQueue = new Queue();
			int routeCount = 0;
			int queueSize;
			int number;
			int i;
			int j;
			Route tempRoute;		//存储从队列头弹出的路径信息

			for(i = 0; i < routeNumber; i++)
			{
				if(routeArray[i].origination == origination)
					routeQueue.Enqueue(routeArray[i]);
			}

			for(number = 1;number < stopNumber; number++)
			{
				queueSize = routeQueue.Count;
				for(j = 1; j <= queueSize; j++)
				{
					tempRoute = (Route)routeQueue.Dequeue();
					for(i = 0; i < routeNumber; i++)
					{
						if(routeArray[i].origination == tempRoute.termination)
							routeQueue.Enqueue(routeArray[i]);
					}
				}
			}

			queueSize = routeQueue.Count;
			for(j = 1; j <= queueSize; j++)
			{
			
				tempRoute = (Route)routeQueue.Dequeue();
				if(tempRoute.termination == termination)
					routeCount++;
			}
			return routeCount;
		}

		static int ShortestRoute(char origination, char termination)
		{//计算从origination到termination的最短路径
			int i, j ,k;
			int[,] CopiedMatrix =  new int[cityNumber, cityNumber];;

			Array.Copy(Matrix, CopiedMatrix, cityNumber*cityNumber);
			for(k = 0; k < cityNumber; k++)
				for(i = 0; i < cityNumber; i++)
					for(j = 0; j < cityNumber; j++)
						if(CopiedMatrix[i,k] + CopiedMatrix[k,j] < CopiedMatrix[i,j])
							CopiedMatrix[i,j] = CopiedMatrix[i,k] + CopiedMatrix[k,j];
			
			return CopiedMatrix[origination-'A', termination-'A'];
		}

		static int ShorterRouteCount(char origination, char termination, int length)
		{//从origination到termination距离小于length的不同路线的数量
			int from = origination-'A';
			int to = termination-'A';
			int middle;
			int count = 0;
			
			if(ShortestRoute(origination, termination) != MAX)
			{
				if(Matrix[from, to] < length)
					count++;
				for(middle = 0; middle < cityNumber; middle++)
				{
					if(Matrix[from, middle] < length)
						count += ShorterRouteCount((char)('A'+middle), termination, length-Matrix[from, middle]);
				}
			}
			return count;
		}

		/// <summary>
		/// 应用程序的主入口点。
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			//
			// TODO: 在此处添加代码以启动应用程序
			//
			Console.Write("请输入城市数目：");
			cityNumber = int.Parse(Console.ReadLine());
			Console.Write("请输入连通图信息：");
			inputString = Console.ReadLine();

			ConvertStrToArray();
			ConvertArrayToMatrix();

			//问题1—5的输出
			string[] stringArray = {"ABC","AD","ADC","AEBCD","AED"};
			int distance;
			foreach(string routeString in stringArray)
			{
				distance = Distance(routeString);
				if(distance == 0)
					Console.WriteLine("路线{0}距离为NO SUCH ROUTE!",  routeString);
				else
					Console.WriteLine("路线{0}距离为{1}", routeString, Convert.ToString(distance));
			}

			//问题6的输出
			int routeCount = RouteCount('C','C',1);
			routeCount += RouteCount('C','C',2);
			routeCount += RouteCount('C','C',3);
			Console.WriteLine("从C城开始到C城结束且最多停顿3次的路线数为{0}",routeCount);

			//问题7的输出
			routeCount = RouteCount('A','C',4);
			Console.WriteLine("从A城开始到C城结束且停顿4次的路线数为{0}",routeCount);

			//问题8，9的输出
			int shortestRoute = ShortestRoute('A','C');
			Console.WriteLine("从A到C最短路线的长度为{0}",shortestRoute);
			shortestRoute = ShortestRoute('B','B');
			Console.WriteLine("从B到B最短路线的长度为{0}",shortestRoute);

			//问题10的输出
			int count = ShorterRouteCount('C', 'C', 30);
			Console.WriteLine("从C到C距离小于30的不同路线的数量为{0}",count);
		}
	}
}