class1.cs

A star 算法求解最短路径问题

using System;
using System.IO;
using System.Collections;

namespace Path_UProject
{
	/// <summary>
	/// Summary description for Class1.
	/// </summary>
	class Class1
	{
		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			int [,] map = new int[10,10];
			TextReader tR = new StreamReader("map.txt");
		
			int i=0,j=0;
		
			foreach(char ch in tR.ReadToEnd())
			{	
				if((ch!=' ')&&(ch!=13)&&(ch!=10))
				{
					int n =(int) double.Parse(ch.ToString());
					map[i,j]=n;
					i++;
					if (i>=10){i=0;j++;}
				}
			}
			tR.Close();

			ArrayList ar = new ArrayList();
			

			int firsti=0,firstj=0;
			for (i=0; i<=9; i++)
				for (j=0; j<=9; j++)
					if(map[i,j]==2){Node n1 = new Node();n1.i=i;n1.j=j;ar.Add(n1);}

			Class1 obj = new Class1();

			Node n2 = (Node)ar[0];
			obj.FindPath(0,0,n2.i,n2.j,ref map);
			Console.WriteLine("\n");

			for ( i=0; i<=ar.Count-2; i++)
			{
				Node n3 = (Node)ar[i];
				Node n4 = (Node)ar[i+1];
				obj.FindPath(n3.i,n3.j,n4.i,n4.j,ref map);
				Console.WriteLine("\n");
			}

			Node n5 = (Node)ar[ar.Count-1];
			obj.FindPath(n5.i,n5.j,0,0,ref map);

		}

		public void FindPath(int starti, int startj, int nexti, int nextj, ref int[,] map)
		{
			ArrayList ar = new ArrayList();
            
			Path p = new Path(nexti,nextj);
			p.AddNode(starti,startj);
			
			ar.Add(p);
			Node nnn=(Node)p.p[p.p.Count-1];

			p=(Path)ar[0];
			ar.RemoveAt(0);
			p.Extend(ref ar, ref map);

			ar.Sort();
			p=(Path)ar[0];
			
			for (;!p.Finished();)
			{
				ar.Sort();
				p=(Path)ar[0];
				ar.RemoveAt(0);
				p.Extend(ref ar, ref map);
				p.ReplaceTheBetter(ref ar);
			}

			for (int it=0; it<=p.p.Count-1;it++)
			{
				nnn=(Node)p.p[it];
				Console.WriteLine("{0} {1}",nnn.i,nnn.j);
			}
		
		}
	}
}