骑士旅行问题java解答

骑士旅游

import java.io.BufferedReader;。

import java.io.InputStreamReader;。

{

private Lattice[] st; //棋盘数组。

private int top;。

//...................................。

public StackX()。

{

st = new Lattice[SIZE];。

top = -1;

}

//............................。

public void push(Lattice j)。

{

st[++top] = j;。

}

//...............。

public Lattice pop()。

{

return st[top--];。

}

//....................。

public Lattice peek()。

{

return st[top];。

}

//.................。

public boolean isEmpty()。

{

return (top == -1);。

}

}

/*

* 棋格的类

*/

class Lattice。

{

public int f;//从前驱棋格的哪个方向而来。

public int x;。

public int y;。

public Lattice(int f,int x,int y)。

{

this.f=f;

this.x=x;

this.y=y;

}

public Lattice getNextLattice(int f,Direction d)。

{

return new Lattice(f,this.x+d.x , this.y+d.y);。

}

}

///////////////////////////////////////////////////////////////////////////。

/*

* 移动的方向

*/

class Direction。

{

public int x;。

public int y;。

public Direction(int x,int y)。

{

this.x=x;

this.y=y;

}

}

//////////////////////////////////////。

class Chess。

{

//参数

private boolean[][] chessBoard ; //棋盘。

int MAX_X = 5; //棋盘宽。

int MAX_Y = 5; //棋盘高。

private int number; //未访问棋格数。

private Lattice[] path;。

private Direction[] direction;//移动方向。

{

direction = new Direction[]。

{new Direction(2, -1) ,new Direction(2, 1),。

new Direction(1, 2),new Direction(-1, 2),。

new Direction(-2, 1),new Direction(-2, -1),。

new Direction(-1, -2),new Direction(1, -2)};。

}

//........................................。

public Chess(int x,int y)。

{

this.MAX_X = x;。

this.MAX_Y = y;。

this.number = MAX_X * MAX_Y; //未访问棋格数。

this.chessBoard = new boolean[MAX_X][MAX_Y];。

for (int i = 0; i < MAX_X; i++)//初始化棋盘。

{

for (int j = 0; j < MAX_Y; j++)。

{

chessBoard[i][j] = false;。

}

}

path = new Lattice[number];。

}

//...............................................。

/*

* 判定给定棋格lattice ,是否在棋盘内,超出范围则不合法。

*/

public boolean isValid(Lattice lattice)。

{

if(lattice.x >= 0 && lattice.y>= 0 && lattice.x

{

return true;。

}

return false;。

}

//..............................................。

/*

* lattice 给定的棋格。

* f 开始遍历的方法。

* 返回lattice 的下一个未访问的后继棋格。

*/

public Lattice getNextUnvisitedLattice(int f,Lattice lattice)。

{

for(int i = f; i

{

Lattice temp = lattice.getNextLattice(i, direction[i]);。

if(isValid(temp))//在棋盘内。

{

if(!chessBoard[temp.x][temp.y]) /没有访问。

{

return temp;。

}

}

}

return null;。

}

///////////////////////////////////////////////////////////。

/*

* 骑士的旅行

* 过程：首先任选一个棋格标记为已访问,并入栈。

* 如果栈不为空

* 找栈顶棋格的后继未访问棋格。

* 如果找到,则后继未访问棋格标记为已访问,并入栈。

* 如果为未找到,则把栈顶元素退栈。

* 如果所有棋格都已入栈,则骑士旅行完成,方法结束。

*/

public void knightTour()。

{

StackX path = new StackX();//存放已经访问的棋格。

path.push(new Lattice(-1, 0, 0)); //从（0,0）开始。

number -- ;。

chessBoard[0][0] = true;。

int f = 0; //方向。

while(!path.isEmpty())。

{

Lattice temp = getNextUnvisitedLattice(f, path.peek());//后继未访问棋格。

if(temp==null) /没找到。

{

Lattice l = path.pop();。

chessBoard[l.x][l.y] = false;。

f = l.f+1; //下一个方向。

number ++;。

}

else //找到。

{

chessBoard[temp.x][temp.y] = true;。

path.push(temp);。

f= 0 ;//下一个方向。

number -- ;。

}

//如果number == 0,说明全部棋格已经入栈,则骑士完成旅行。

if(number == 0)。

{

int j = this.path.length-1;。

while(!path.isEmpty()) //把栈中棋格转化为数组。

{

this.path[j--] = path.pop();。

}

disPlayKnightTour(); //显示旅行路径。

System.out.println('成功找到骑士旅行路径');。

return;

}

}

System.out.println('失败,没有找到骑士旅行路径');。

}

//显示骑士旅行路径。

public void disPlayKnightTour()。

{

for(int i=0;i

{

for(int k =0;k

{

chessBoard[i][k] = false;。

}

}

for(int i =0;i

{

Lattice temp = path[i];。

chessBoard[temp.x][temp.y] = true;。

disPlayChessBoard();。

}

}

//....................................。

public void disPlayChessBoard()。

{

System.out.print(' ');。

for (int i = 0; i < MAX_X; i++)。

{

System.out.print(' '+i);。

}

System.out.println();。

for (int i = 0; i < MAX_X; i++)。

{

System.out.println(' '+i);。

for (int j = 0; j < MAX_Y; j++)。

{

if(chessBoard[i][j] == false)。

{

System.out.print('O');。

}

else

{

System.out.print('*');。

}

}

System.out.println();。

}

System.out.println();。

}

}

/////////////////////////////////。

public class Knight。

{

public static void main(String[] args) throws Exception。

{

System.out.println('请输入棋盘的宽：');。

int x = getInt();。

System.out.println('请输入棋盘的高:');。

int y = getInt();。

Chess chess = new Chess(x, y);。

chess.knightTour();。

}

//.......................................。

public static String getString() throws Exception。

{

InputStreamReader isr = new InputStreamReader(System.in);。

BufferedReader br = new BufferedReader(isr);。

String s = br.readLine();。

return s;。

}

//.....................。

public static int getInt() throws Exception。

{

String s = getString();。

return Integer.parseInt(s);。

}

}