import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Scanner;
import java.util.LinkedList;




public class AStar
{


	/**
	 * This class represents a state in your search space.
	 * It should contain whatever you need to track for the problem
	 */
	public class State implements Comparable<State>
	{

		/** Constructor should contain anything you need to track
		 * about a state.
		 * */
		public State() //Add Params as needed
		{
			//DEFINE
		}


		/**
		 * Return the cost thus far to reach this state
		 */
		double getCost()
		{ //DEFINE
		}

		/**
		 * Return the heurisitc value
		 *
		 * The heuristic is an estimate of how much cost
		 * it will take to go from here to the goal state.
		 *
		 * If you don't wish to write one, you can simply return 0
		 * to not use a heurisitc.  A heurisitc just speeds up the finding
		 * of the correct path.
		 *
		 * This must be an underestimate or exactly correct or the algorithm's
		 * result might not be optimal.
		 *
		 * Must also avoid triangle inequality problem, but that is rare.
		 *
		 *
		 */
		double getHeur()
		{
			return 0.0;
		}

		/** returns the total cost to reach goal.
		 *
		 * This is cost thus far plus the heurisitc estimate 
		 */
		double getEstimate()
		{
			return getCost() + getHeur();
		}


		/**
		 * Add the next states the priority queue (Q).
		 *
		 * The states should have updated costs and whatever other
		 * data needs to be tracked.
		 *
		 * Don't worry about duplicates, the search function handles those
		 */
		void next(PriorityQueue<State> Q)
		{
			//DEFINE

		}

		/** returns true iff this is the goal state */
		boolean isGoal()
		{
			//DEFINE
		}

		/** sorts by estimated cost (lowest cost first) 
		 * 
		 * using this the priority queue will be able to expand the lowest cost estimate
		 * elements first.
		 * */
		public int compareTo(State O)
		{
			double z=getEstimate();
			double oz=O.getEstimate();

			if (z < oz) return -1;
			if (z > oz) return 1;

			return 0;
			
		}


		/**
		 * returns a string that has the needed unique data for this state
		 *  
		 *  Used for the state visited list.  If two states return the same string,
		 *  they are assumed to represent the same state and only the lowest cost
		 *  of these will be considered.
		 *
		 *  This avoids expanding
		 */
		public String toString()
		{
			//DEFINE

		}


	}


	/**
	 * This is the actual search.
	 * None of the code here should need to be changed.
	 *
	 * Starting from the given start_state, searches for a state where
	 * isGoal() is true.  Returns the lowest cost one.  If there are multiple
	 * of the same cost, one is returned.
	 *
	 * Returns null if no goal state is found.
	 *
	 */
	public State search(State start_state)
	{
		PriorityQueue<State> Q=new PriorityQueue<State>();

		Q.add(start_state);

		HashSet<String> visited=new HashSet<String>(4096,0.5f);

		while(Q.peek()!=null)
		{
			State s=Q.poll();

			if (s.isGoal()) return s;

			String str=s.toString();
			if (!visited.contains(str))
			{
				visited.add(str);

				s.next(Q);

			}
		}
		return null;

	}
}