骑士巡游问

import java.util.Vector;

public class class03{

public static void main(String[] args){

node root=new node(null,4,4);

node leaf=DepthFirstSearch(root);

leaf.display();

}

static node DepthFirstSearch(node curNode){

if(curNode.depth==64) return curNode;

node[] sons=curNode.getSons();

if(sons==null) return null;

for(int i=0;i<sons.length;i++){

node n=DepthFirstSearch(sons[i]);

if(n!=null) return n;

}

return null;

}

}

class node{

int depth;

int[][] Grid=new int[8][8];

node father;

node[] sons;

int x,y;

node(node father,int x,int y){

this.father=father; this.x=x;this.y=y;

if(this.father==null) this.depth=1;

else this.depth=this.father.depth+1;

if(this.father==null){

this.Grid[x][y]=1;

}

else{

for(int i=0;i<this.Grid.length;i++)

for(int j=0;j<this.Grid[i].length;j++)

this.Grid[i][j]=this.father.Grid[i][j];

this.Grid[x][y]=this.depth;

}

}

public node[] getSons(){

if(sons==null) this.setSons();

return this.sons;

}

public void setSons(){

Vector v=new Vector();

if(x-2>=0 && y+1<8 && Grid[x-2][y+1]==0) v.add(new node(this,x-2,y+1));

if(x-1>=0 && y+2<8 && Grid[x-1][y+2]==0) v.add(new node(this,x-1,y+2));

if(x+1<8 && y+2<8 && Grid[x+1][y+2]==0) v.add(new node(this,x+1,y+2));

if(x+2<8 && y+1<8 && Grid[x+2][y+1]==0) v.add(new node(this,x+2,y+1));

if(x+2<8 && y-1>=0 && Grid[x+2][y-1]==0) v.add(new node(this,x+2,y-1));

if(x+1<8 && y-2>=0 && Grid[x+1][y-2]==0) v.add(new node(this,x+1,y-2));

if(x-1>=0 && y-2>=0 && Grid[x-1][y-2]==0) v.add(new node(this,x-1,y-2));

if(x-2>=0 && y-1>=0 && Grid[x-2][y-1]==0) v.add(new node(this,x-2,y-1));

if(v.size()>0){

sons=new node[v.size()];

sons=(node[])v.toArray(sons);

for(int i=0;i<sons.length;i++)

for(int j=0;j<sons.length-i-1;j++)

if(sons[j].getSkipCount()>sons[j+1].getSkipCount()){

node temp=sons[j];

sons[j]=sons[j+1];

sons[j+1]=temp;

}

}

}

int getSkipCount(){

int count=0;

if(x-2>=0 && y+1<8 && Grid[x-2][y+1]==0) count++;

if(x-1>=0 && y+2<8 && Grid[x-1][y+2]==0) count++;

if(x+1<8 && y+2<8 && Grid[x+1][y+2]==0) count++;

if(x+2<8 && y+1<8 && Grid[x+2][y+1]==0) count++;

if(x+2<8 && y-1>=0 && Grid[x+2][y-1]==0) count++;

if(x+1<8 && y-2>=0 && Grid[x+1][y-2]==0) count++;

if(x-1>=0 && y-2>=0 && Grid[x-1][y-2]==0) count++;

if(x-2>=0 && y-1>=0 && Grid[x-2][y-1]==0) count++;

return count;

}

void display(){

for(int i=0;i<Grid.length;i++){

for(int j=0;j<Grid[i].length;j++)

System.out.print(Grid[i][j]+" ");

System.out.println();

}

}

}