block.java

该算法首先根据输入的节点数（该程序可选的有3X3

	 	 	 	        	 int i;
	 	 	 	        	 for(i=0;i<4;i++)if(p.childBlock[i]==null)break;
	 	 	 	        	 p.childBlock[i]=new Block(xBlock);
	 	 	 	        	}
	 	 	 	        xBlock[space+1]=xsBlock[space+1].toString();	
	 	 	 	        break;
	 	 	 	}
	 	 	  if(p.length()>0&&d<dm){d++;j=0;p=p.childBlock[j];}
	 	 	  else if(p.length()<=0){ 
	 	 	    j++;
	 	 	    p=findParent(p,this);
	 	 	    if(j<p.length()){p=p.childBlock[j];}
	 	 	    else{
	 	 	       while((p=findParent(p,this))!=null){
	 	 	          int i;
	 	 	          d--;
	 	 	          for(i=0;i<p.length();i++)
	 	 	            if(p.childBlock[i].access==0)break;
	 	 	          if(i<p.length()){d++;j=i;p=p.childBlock[j];break;}  
	 	 	         } 
	 	 	       if(p==null){
	 	 	 	 	 if((p=findNotAccess(this))==null)return false;
	 	 	 	 	 else if((d=blockLayer(this,p.blockString,0))>dm){System.out.print("<"+d+">");return false;}
	 	 	 	 	 else j=mountChild(p);
	 	 	 	 	}
	 	 	      }
	 	 	 }
	 	 	 else {
	 	 	 	 while((p=findParent(p,this))!=null){
	 	 	 	 	 int i;
	 	 	          d--;
	 	 	          for(i=0;i<p.length();i++)
	 	 	            if(p.childBlock[i].access==0)break;
	 	 	          if(i<p.length()&&d<dm){d++;j=i;p=p.childBlock[j];break;}  
	 	 	 	 	}
	 	 	 	 if(p==null){
	 	 	 	 	 if((p=findNotAccess(this))==null)return false;
	 	 	 	 	 else if((d=blockLayer(this,p.blockString,0))>dm){System.out.print("("+d+")");return false;}
	 	 	 	 	 else j=mountChild(p);
	 	 	 	 	}
	 	 	 	}
	 	 	}
	 	 if(complete(p.blockString,yBlock)){this.dm=dm;return true;}
	 	 else return false;
	 	}
	 	
	 public Block findNotAccess(Block p){
	 	 Block x;
	 	 if(p.access==0)return p;
	 	 else{
	 	 	 for(int i=0;i<p.length();i++)
	 	 	   if((x=findNotAccess(p.childBlock[i]))!=null)return x;
	 	 	}
	 	 return null;	
	 	}
	 	
	 public int blockLayer(Block p,String []yBlock,int n){
	 	 int x;
	 	 if(complete(p.blockString,yBlock))return n;
	 	 else{
	 	 	 for(int i=0;i<p.length();i++)if((x=blockLayer(p.childBlock[i],yBlock,++n))!=-1)return x;
	 	 	}
	 	 return -1;
	 	}
	 	
	 public int mountChild(Block p){
	 	 Block t=findParent(p,this);
	 	 for(int i=0;i<t.length();i++)
	 	   if(complete(p.blockString,t.childBlock[i].blockString))return i;
	 	 return -1;
	 	}
	 	
	 public void transRoute(String []yBlock){
	 	 int i=0;
	 	 this.route=new Block[this.dm+1];
	 	 this.route[i]=findBlock(yBlock,this);
	 	 while(!complete(this.route[i].blockString,this.blockString)){
	 	 	 i++;
	 	 	 route[i]=findParent(route[i-1],this);
	 	 	}
	 	}
	 	
	 public void reverseRoute(){
	 	 int i,l;
	 	 Block t;
	 	 for(i=0;i<this.route.length&&this.route[i]!=null;i++);
	 	 l=i;
	 	 for(i=0;i<=(l-1)/2;i++){
	 	   t=this.route[i];
	 	   this.route[i]=this.route[l-1-i];
	 	   this.route[l-1-i]=t;
	 	  } 
	 	}
	 	
	 public int lengthRoute(){
	 	 int i;
	 	 for(i=0;i<this.route.length&&this.route[i]!=null;i++);
	 	 return i;
	 	}
	 	
	 public int numBlock(){
	 	 return this.blockString.length;
	 	}
	 	
	 private Block findBlock(String []yBlock,Block q){
	 	 Block x;
	 	 if(complete(q.blockString,yBlock))return q;
	 	 else{
	 	 	 for(int i=0;i<q.length();i++)if((x=findBlock(yBlock,q.childBlock[i]))!=null)return x;
	 	 	}
	 	 return null;
	 	}
	 	
	 private Block findParent(Block p,Block q){
	 	 Block x;
	 	 if(q.length()<=0)return null;
	 	 for(int i=0;i<q.length();i++)
	 	   if(complete(q.childBlock[i].blockString,p.blockString))return q;
	 	 for(int i=0;i<q.length();i++){
	 	 	 if((x=findParent(p,q.childBlock[i]))!=null)return x;
	 	 	}
	 	 return null;	
	 	}
	 	
	 private int length(){
	 	 int i=0;
	 	 while(i<this.childBlock.length&&this.childBlock[i]!=null)i++;
	 	 return i;
	 	}	
	 	
	 private boolean insertOK(Block p,String []xBlock){
	 	 if(complete(p.blockString,xBlock))return false;
	 	 for(int i=0;i<p.childBlock.length;i++){
	 	 	 if(p.childBlock[i]!=null&&insertOK(p.childBlock[i],xBlock)==false)return false;
	 	 	 else continue;
	 	 	}
	 	 return true;	
	 	}
	 				 	
	 private int stateSpace(String []xBlock){
	 	 int space=placeSpace(xBlock);
	 	 int blockN=(int)Math.sqrt(xBlock.length);
	 	 if(space==0)return 0;
	 	 if(space==blockN-1)return 1;
	 	 if(space==xBlock.length-blockN)return 2;
	 	 if(space==xBlock.length-1)return 3;
	 	 if(space>0&&space<blockN-1)return 4;
	 	 if(space>xBlock.length-blockN&&space<xBlock.length-1)return 7;
	 	 if(space%blockN==0)return 5;
	 	 if((space+1)%blockN==0)return 6;
	 	 return 8;
	 	}
	 	
	 private int placeSpace(String []xBlock){
	 	 for(int i=0;i<xBlock.length;i++)
	 	   if(xBlock[i].equals(""))return i;
	 	 return 82;
	 	}		
	 	
	 private boolean complete(String []xBlock,String []yBlock){
	 	 for(int i=0;i<xBlock.length;i++)
	 	   if(!xBlock[i].equals(yBlock[i]))return false;
	 	 return true;   
	    }
	    
	 public void display(){
	 	 for(int i=0;i<this.blockString.length;i++){
	 	   System.out.print(this.blockString[i]+" ");
	 	   if(this.blockString[i].equals(""))System.out.print(" ");
	 	   if((i+1)%((int)Math.sqrt(this.blockString.length))==0)System.out.println();
	 	  }
	 	 System.out.println();  
	 	}
	 	
	 public void displayRoute(){
	 	 System.out.println("The route is");
	 	 for(int i=0;i<this.route.length&&this.route[i]!=null;i++) 
	 	    this.route[i].display();
	 	}
	 	
	 public void displayTree(Block t){
	 	 t.display();
	 	 for(int i=0;i<t.childBlock.length;i++)
	 	   displayTree(t.childBlock[i]);
	 	}
	}
	
class testBlock{
	 public static void main(String args[]){
	 	 Block x;
	 	 boolean t;
	 	 String []xBlock=new String[9];
	 	 String []yBlock=new String[9];
	 	 xBlock[0]="8";xBlock[1]="4";xBlock[2]="7";xBlock[3]="2";xBlock[4]="";
	 	 xBlock[5]="3";xBlock[6]="6";xBlock[7]="1";xBlock[8]="5";
	 	 yBlock[0]="1";yBlock[1]="2";yBlock[2]="3";yBlock[3]="8";yBlock[4]="";
	 	 yBlock[5]="4";yBlock[6]="7";yBlock[7]="6";yBlock[8]="5";   
	 	 x=new Block(xBlock);
	 	 System.out.print((t=x.createBlockTree(yBlock,6)));
	 	 if(t){x.transRoute(yBlock);
	 	     x.reverseRoute();
	 	     x.displayRoute();
	 	   }
	 	}
	}