import?java.util.ArrayList;
import?java.util.Comparator;
import?java.util.Iterator;
import?java.util.List;
import?java.util.PriorityQueue;


public?class?astar?{
	
	public?static?void?main（String?args[]）
	{
		int[][]?startStatus={{231}{508}{467}};
		int[][]?endStatus?=?{{123}{456}{780}};
		//int[][]?endStatus?=?{{231}{587}{460}};
		AstarDoer?test?=?new?AstarDoer（startStatusendStatus）;
		test.run（）;
	}

}
class?AstarDoer
{
	int[][]?startStatus;
	int[][]?endStatus;
	NodeComparator?cmp?=?new?NodeComparator（）;??
	PriorityQueue?open?=?new?PriorityQueue?（1000000cmp）;??
	PriorityQueue??close?=new?PriorityQueue?（1000000cmp）;??
	public?AstarDoer（int[][]?startStatusint[][]?endStatus?）
	{
		this.startStatus?=?new?int[3][3];
		this.endStatus?=?new?int[3][3];
		for（int?i=0;i<3;i++）
		{
			for（int?j=0;j<3;j++）
			{
				this.startStatus[i][j]?=?startStatus[i][j];
				this.endStatus[i][j]?=?endStatus[i][j];
			}
		}
	}
	private?int?getReverse（int[][]?status）
	{
		int?reverse=0;
		for（int?i=0;i<9;i++）
		{
			for（int?j=i+1;j<9;j++）
			{
				int?k?=?i/3;
				int?m?=?i%3;
				if（status[k][m]>status[j/3][j%3]）
				{
					reverse+=1;
				}
			}
		}
		return?reverse;
	}
	private?boolean?check（int[][]?startStatusint[][]?endStatus）
	{
		int?getS?=0;
		int?getE?=0;
		getS?=?getReverse（startStatus）;
		getE?=?getReverse（endStatus）;
		if（（getS%2）?==?（getE%2）?）
		{
			return?true;
		}
		return?false;
	}
	private?void?initStart（）
	{
		Node?startNode?=?new?Node（startStatus）;
		startNode.gvalue?=?0;
		startNode.parent?=?null;
		startNode.hvalue?=?startNode.getH（endStatus）;
		startNode.fvalue?=?startNode.gvalue+startNode.hvalue;
		open.add（startNode）;
	}
	private?boolean?isInList（Node?lNodeNode?newNodeParent）
	{
		while（newNodeParent?!=?null）
		{
			if（lNode.equal（newNodeParent.status））
			{
				return?true;
			}
			newNodeParent?=?newNodeParent.parent;
		}
		return?false;
	}
	private?void?initChild（Node?newNodeList?newNodeChild?）
	{
		int?whiteSpace?=?0;
		whiteSpace?=?newNode.getWhitespace（）;
		/*得到空格位置判斷左移產生節點*/
		if（（whiteSpace%3）?!=2）
		{
			Node?lNode?=?new?Node（newNode.status）;
			lNode.status[whiteSpace/3][whiteSpace%3]?=?lNode.status[whiteSpace/3][（whiteSpace%3）+1];
			lNode.status[whiteSpace/3][（whiteSpace%3）+1]?=?0;
			if（isInList（lNodenewNode.parent）?==?false）
			{
				lNode.parent?=?newNode;
				lNode.gvalue?=?newNode.gvalue+1;
				lNode.hvalue?=?lNode.getH（endStatus）;
				lNode.fvalue?=?lNode.gvalue+lNode.hvalue;
				newNodeChild.add（lNode）;
			}
				
			
		}
		/*得到空格位置判斷右移產生節點*/
		if（（whiteSpace%3）?!=0）
		{
			Node?lNode?=?new?Node（newNode.status）;
			lNode.status[whiteSpace/3][whiteSpace%3]?=?lNode.status[whiteSpace/3][（whiteSpace%3）-1];
			lNode.status[whiteSpace/3][（whiteSpace%3）-1]?=?0;
			if（isInList（lNodenewNode.parent）?==?false）
			{
				lNode.parent?=?newNode;
				lNode.gvalue?=