数据结构课程设计之马踏棋盘（非递归实现）
//马踏棋盘,要求走遍棋盘所有方格，用非递归实现，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());
}
}
评论0