class MazeSolver
	{
        public string ToString(int fromx, int fromy, int tox, int toy)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
            {
                for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
                {
                    if (x == fromx && y == fromy)
                    {
                        sb.Append("S");
                    }
                    else if (x == tox && y == toy)
                    {
                        sb.Append("E");
                    }
                    else
                    {
                        sb.Append(this[x, y]);
                    }
                }
                sb.Append(Environment.NewLine);
            }
            return sb.ToString();
        }
        public string PathToString(int[,] solved)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
            {
                for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
                {
                    if (solved[x,y]==100)
                    {
                        sb.Append("+");
                    }
                    else
                    {
                        sb.Append(solved[x, y]);
                    }
                }
                sb.Append(Environment.NewLine);
            }
            return sb.ToString();
        }

        /// <summary>
        /// Class attributes/members
        /// </summary>
        int[,] m_iMaze;
		int m_iRows;
		int m_iCols;
		int iPath=100;
		bool diagonal=false;
		public event MazeChangedHandler OnMazeChangedEvent;

		/// <summary>
		/// Constructor 1: takes a 2D integer array
		/// </summary>
		public MazeSolver(int[,] iMaze)
		{
			m_iMaze=iMaze;
			m_iRows=iMaze.GetLength(0);
			m_iCols=iMaze.GetLength(1);
		}

		/// <summary>
		/// Constructor 2: initializes the dimensions of maze, 
		/// later, indexers may be used to set individual elements' values
		/// </summary>
		public MazeSolver(int iRows, int iCols)
		{
			m_iMaze=new int[iRows, iCols];
			m_iRows=iRows;
			m_iCols=iCols;
		}
			
		/// <summary>
		/// Properites:
		/// </summary>
		public int Rows
		{
			get { return m_iRows; }
		}

		public int Cols
		{
			get { return m_iCols; }
		}
		public int[,] GetMaze
		{
			get { return m_iMaze; }
		}
		public int PathCharacter
		{
			get { return iPath; }
			set
			{
				if (value==0)
					throw new Exception("Invalid path character specified");
				else
					iPath=value;
			}
		}
		public bool AllowDiagonals
		{
			get {	return diagonal;	}
			set {	diagonal=value;		}
		}


		/// <summary>
		/// Indexer
		/// </summary>
		public int this[int iRow, int iCol]
		{
			get { return m_iMaze[iRow,iCol]; }
			set 
			{ 
				m_iMaze[iRow,iCol]=value;
				if (this.OnMazeChangedEvent!=null)	// trigger event
					this.OnMazeChangedEvent(iRow, iCol);
			}
		}

		/// <summary>
		/// The function is used to get the contents of a given node in a given maze,
		///  specified by its node no.
		/// </summary>
		private int GetNodeContents(int[,] iMaze, int iNodeNo)
		{
			int iCols=iMaze.GetLength(1);
			return iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols];
		}

		/// <summary>
		/// The function is used to change the contents of a given node in a given maze,
		///  specified by its node no.
		/// </summary>
		private void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
		{
			int iCols=iMaze.GetLength(1);
			iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols]=iNewValue;
		}
		
		/// <summary>
		/// This public function finds the shortest path between two points
		/// in the maze and return the solution as an array with the path traced 
		/// by "iPath" (can be changed using property "PathCharacter")
		/// if no path exists, the function returns null
		/// </summary>
		public int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
		{
			int iBeginningNode = iFromY*this.Cols + iFromX;
			int iEndingNode = iToY*this.Cols + iToX;
			return ( Search(iBeginningNode, iEndingNode) ) ;
		}

	
		/// <summary>
		/// internal function for that finds the shortest path using a technique
		/// similar to breadth-first search.
		/// It assigns a node no. to each node(2D array element) and applies the algorithm
		/// </summary>
		private enum Status
		{	Ready,	Waiting,	Processed	}
		private int[,] Search(int iStart, int iStop)
		{
			const int empty=0;
		
			int iRows=m_iRows;
			int iCols=m_iCols;
			int iMax=iRows*iCols;
			int[] Queue=new int[iMax];
			int[] Origin=new int[iMax];
			int iFront=0, iRear=0;

			//check if starting and ending points are valid (open)
			if ( GetNodeContents(m_iMaze, iStart)!=empty || GetNodeContents(m_iMaze, iStop)!=empty )
			{
				return null;
			}
		
			//create dummy array for storing status
			int[,] iMazeStatus=new int[iRows,iCols];
			//initially all nodes are ready
			for(int i=0;i<iRows;i++)
				for(int j=0;j<iCols;j++)
					iMazeStatus[i,j]=(int)Status.Ready;

			//add starting node to Q
			Queue[iRear]=iStart; 
			Origin[iRear]=-1; 
			iRear++;
			int iCurrent, iLeft, iRight, iTop, iDown, iRightUp, iRightDown, iLeftUp, iLeftDown;
			while(iFront!=iRear)	// while Q not empty	
			{
				if (Queue[iFront]==iStop)		// maze is solved
					break;

				iCurrent=Queue[iFront];
			
				iLeft=iCurrent-1;
				if (iLeft>=0 && iLeft/iCols==iCurrent/iCols) 	//if left node exists
					if ( GetNodeContents(m_iMaze, iLeft)==empty ) 	//if left node is open(a path exists)
						if (GetNodeContents(iMazeStatus, iLeft) == (int)Status.Ready)	//if left node is ready
						{
							Queue[iRear]=iLeft; //add to Q
							Origin[iRear]=iCurrent;
							ChangeNodeContents(iMazeStatus, iLeft, (int)Status.Waiting); //change status to waiting
							iRear++;
						}

				iRight=iCurrent+1;
				if (iRight<iMax && iRight/iCols==iCurrent/iCols) 	//if right node exists
					if ( GetNodeContents(m_iMaze, iRight)==empty ) 	//if right node is open(a path exists)
						if (GetNodeContents(iMazeStatus, iRight) == (int)Status.Ready)	//if right node is ready
						{
							Queue[iRear]=iRight; //add to Q
							Origin[iRear]=iCurrent;
							ChangeNodeContents(iMazeStatus, iRight, (int)Status.Waiting); //change status to waiting
							iRear++;
						}
		
				iTop=iCurrent-iCols;
				if (iTop>=0 ) 	//if top node exists
					if ( GetNodeContents(m_iMaze, iTop)==empty ) 	//if top node is open(a path exists)
						if (GetNodeContents(iMazeStatus, iTop) == (int)Status.Ready)	//if top node is ready
						{
							Queue[iRear]=iTop; //add to Q
							Origin[iRear]=iCurrent;
							ChangeNodeContents(iMazeStatus, iTop, (int)Status.Waiting ); //change status to waiting
							iRear++;
						}

				iDown=iCurrent+iCols;
				if (iDown<iMax ) 	//if bottom node exists
					if ( GetNodeContents(m_iMaze, iDown)==empty ) 	//if bottom node is open(a path exists)
						if (GetNodeContents(iMazeStatus, iDown) == (int)Status.Ready)	//if bottom node is ready
						{
							Queue[iRear]=iDown; //add to Q
							Origin[iRear]=iCurrent;
							ChangeNodeContents(iMazeStatus, iDown, (int)Status.Waiting); //change status to waiting
							iRear++;
						}
				if (diagonal==true)
				{
					iRightDown=iCurrent+iCols+1;
					if (iRightDown<iMax && iRightDown>=0 && iRightDown/iCols==iCurrent/iCols+1 ) 	//if bottom-right node exists
						if ( GetNodeContents(m_iMaze, iRightDown)==empty ) 	//if this node is open(a path exists)
							if (GetNodeContents(iMazeStatus, iRightDown) == (int)Status.Ready)	//if this node is ready
							{
								Queue[iRear]=iRightDown; //add to Q
								Origin[iRear]=iCurrent;
								ChangeNodeContents(iMazeStatus, iRightDown, (int)Status.Waiting); //change status to waiting
								iRear++;
							}

					iRightUp=iCurrent-iCols+1;
					if (iRightUp>=0 && iRightUp<iMax && iRightUp/iCols==iCurrent/iCols-1) 	//if upper-right node exists
						if ( GetNodeContents(m_iMaze, iRightUp)==empty ) 	//if this node is open(a path exists)
							if (GetNodeContents(iMazeStatus, iRightUp) == (int)Status.Ready)	//if this node is ready
							{
								Queue[iRear]=iRightUp; //add to Q
								Origin[iRear]=iCurrent;
								ChangeNodeContents(iMazeStatus, iRightUp, (int)Status.Waiting); //change status to waiting
								iRear++;
							}

					iLeftDown=iCurrent+iCols-1;
					if (iLeftDown<iMax && iLeftDown>=0 && iLeftDown/iCols==iCurrent/iCols+1) 	//if bottom-left node exists
						if ( GetNodeContents(m_iMaze, iLeftDown)==empty ) 	//if this node is open(a path exists)
							if (GetNodeContents(iMazeStatus, iLeftDown) == (int)Status.Ready)	//if this node is ready
							{
								Queue[iRear]=iLeftDown; //add to Q
								Origin[iRear]=iCurrent;
								ChangeNodeContents(iMazeStatus, iLeftDown, (int)Status.Waiting); //change status to waiting
								iRear++;
							}

					iLeftUp=iCurrent-iCols-1;
					if (iLeftUp>=0 && iLeftUp<iMax && iLeftUp/iCols==iCurrent/iCols-1) 	//if upper-left node exists
						if ( GetNodeContents(m_iMaze, iLeftUp)==empty ) 	//if this node is open(a path exists)
							if (GetNodeContents(iMazeStatus, iLeftUp) == (int)Status.Ready)	//if this node is ready
							{
								Queue[iRear]=iLeftUp; //add to Q
								Origin[iRear]=iCurrent;
								ChangeNodeContents(iMazeStatus, iLeftUp, (int)Status.Waiting); //change status to waiting
								iRear++;
							}
				}


				//change status of current node to processed
				ChangeNodeContents(iMazeStatus, iCurrent, (int)Status.Processed);
				iFront++;
			
			}

			//create an array(maze) for solution
			int[,] iMazeSolved=new int[iRows,iCols];
			for(int i=0;i<iRows;i++)
				for(int j=0;j<iCols;j++)
					iMazeSolved[i,j]=m_iMaze[i,j];

			//make a path in the Solved Maze
			iCurrent=iStop;
			ChangeNodeContents(iMazeSolved, iCurrent, iPath);
			for(int i=iFront; i>=0; i--)
			{
				if (Queue[i]==iCurrent)
				{
					iCurrent=Origin[i];
					if (iCurrent==-1)		// maze is solved
						return ( iMazeSolved );
					ChangeNodeContents(iMazeSolved, iCurrent, iPath);
				}
			}
            
			//no path exists
			return null;
		}
	}