马踏棋盘2.txt

数据结构课程设计之马踏棋盘（非递归实现）

数据结构课程设计之马踏棋盘（非递归实现）
//马踏棋盘,要求走遍棋盘所有方格，用非递归实现，closed表和open表都用stack实现，closed表示已经走过的路径，open表时还没考察过的节点以待悔棋时考察
import java.util.*;
class Node{
 int x;
 int y;
 boolean visited;
 int child;
 public Node(int a,int b,boolean c,int d){
  x=a;y=b;visited=c;child=d;
 } 
}
class Chess2 {
 Stack<Node> open=new Stack<Node>();
 Stack<Node> closed=new Stack<Node>();
 int[] moveX={-2,-1,1,2,2,1,-1,-2};
 int[] moveY={1,2,2,1,-1,-2,-2,-1};
 Node[][] chess=new Node[8][8];
 int cinx;
 int ciny;
 Scanner reader=new Scanner(System.in);
 int count=1;
 int test=0;
 
 public Chess2(){
  for(int i=0;i<8;i++)
   for(int j=0;j<8;j++){
    chess[i][j]=new Node(i,j,false,0); 
   } 
 }
 void input(){
  System.out.print("cin>>x:");
  cinx=reader.nextInt();
  System.out.print("cin>>y:");
  ciny=reader.nextInt(); 
  reader.close();
 }
 void search(){
  open.add(chess[cinx][ciny]);
  closed.add(open.pop());
  chess[cinx][ciny].visited=true;
//  System.out.println("open:"+open.size()+" closed:"+closed.size());
  int flag;
 // int compare=8;
  try{
   while(count<62){
    int a,b;
    flag=open.size();
    for(int i=0;i<8;i++){
     a=cinx+moveX[i];
     b=ciny+moveY[i];
    // if(compare>i){
      if(a>=0 && a<8){
       if(b>=0 && b<8){
        if(!chess[a][b].visited){
         open.add(chess[a][b]);
         //flag=true;
         chess[cinx][ciny].child++;
        }
       }
      }
    // }
     
    }
    Node temp;
    if(flag==open.size()){
     temp=closed.pop();
     temp.visited=false;
    // compare=temp.direction;
     System.out.println();
     System.out.println(temp.x+","+temp.y+" "+(count-1)+"<--");
     count--;
     test++;
     closed.peek().child--;
     while(closed.peek().child==0){
      temp=closed.pop();
      temp.visited=false;
      closed.peek().child--;
      System.out.println(temp.x+","+temp.y+" "+(count-1)+"<--");
      count--;
     }
  //   cinx=closed.peek().x;
  //   ciny=closed.peek().y;
     
     
    }
     
     //System.out.println(temp.x+","+temp.y);
   // }else{
     temp=open.pop();
     while(temp.visited){
      temp=open.pop();
     }
      
     closed.add(temp);
     count++;
     System.out.println(temp.x+","+temp.y+" "+(count-1));
     temp.visited=true;
     cinx=temp.x;
     ciny=temp.y; 
  //  }
    
   // flag=false;
//    System.out.print(cinx+","+ciny+">>> ");
//    System.out.println("open:"+open.size()+" closed:"+closed.size());
   }
  }catch(Exception ex){
   System.out.println(ex.toString());
  }
   
  for(int i=0;i<closed.size();i++){
   System.out.print(closed.get(i).x+","+closed.get(i).y+" "+i+"-->");
  }
  System.out.println(closed.size()+" "+count+" "+test+" "+open.size());
 }
}