《Java数据结构跟算法》第二版 Robert lafore 编程作业 第十三章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第十三章
《Java数据结构和算法》第二版 Robert lafore 编程作业 第十三章
/*
13.1 修改bfs.java程序（清单13.2），通过广度优先搜索找到最小生成树，在
mst.java程序（清单13.3）中，这个工作是由深度优先搜索完成的。在
main()中，创建带有9个顶点和12条边的图，然后找到最小生成树。
*/
package chap13.pp1;
// bfs.java
// demonstrates breadth-first search
// to run this program: C>java BFSApp
////////////////////////////////////////////////////////////////
class Queue {
private final int SIZE = 20;
private int[] queArray;
private int front;
private int rear;
// -------------------------
public Queue() // constructor
{
queArray = new int[SIZE];
front = 0;
rear = -1;
}
// -------------------------
public void insert(int j) // put item at rear of queue
{
if (rear == SIZE - 1)
rear = -1;
queArray[++rear] = j;
}
// -------------------------
public int remove() // take item from front of queue
{
int temp = queArray[front++];
if (front == SIZE)
front = 0;
return temp;
}
// -------------------------
public boolean isEmpty() // true if queue is empty
{
return (rear + 1 == front || (front + SIZE - 1 == rear));
}
// -------------------------
} // end class Queue
// //////////////////////////////////////////////////////////////
class Vertex {
public char label; // label (e.g. 'A')
public boolean wasVisited;
// -------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// -------------------------
} // end class Vertex
// //////////////////////////////////////////////////////////////
class Graph {
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private Queue theQueue;
// ------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++)
// set adjacency
for (int k = 0; k < MAX_VERTS; k++)
// matrix to 0
adjMat[j][k] = 0;
theQueue = new Queue();
} // end constructor
// -------------------------
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
// -------------------------
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
// -------------------------
// ===============================================================
// 编程作业 13.1
public void mst() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
// displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2;
while (!theQueue.isEmpty()) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while ((v2 = getAdjUnvisitedVertex(v1)) != -1) { // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v1);
displayVertex(v2); // display it
System.out.print(" ");
theQueue.insert(v2); // insert it
} // end while
} // end while(queue not empty)
// queue is empty, so we're done
for (int j = 0; j < nVerts; j++)
// reset flags
vertexList[j].wasVisited = false;
} // end bfs()
// -------------------------
// ===============================================================
// returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++)
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
return j;
return -1;
} // end getAdjUnvisitedVertex()
// -------------------------
} // end class Graph
// //////////////////////////////////////////////////////////////
public class MSTApp {
public static void main(String[] args) {
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for bfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(0, 2); // AC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(0, 4); // AE
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(1, 3); // BD
theGraph.addEdge(1, 4); // BE
theGraph.addEdge(2, 3); // CD
theGraph.addEdge(2, 4); // CE
theGraph.addEdge(3, 4); // DE
System.out.print("Minimum spanning tree: ");
theGraph.mst(); // minimum spanning tree
System.out.println();
} // end main()
} // end class BFSApp
// //////////////////////////////////////////////////////////////
/*
13.2 修改dfs.java程序（清单13.1），用邻接表而不是邻接矩阵执行深度优先
搜索。可以通过修改第5章linkList2.java程序（清单5.2）的Link类和
LinkList类得到链表。修改LinkList中的find()方法，搜索一个未访问的
顶点，而不是一个关键字值。
*/
package chap13.pp2;
// dfs.java
// demonstrates depth-first search
// to run this program: C>java DFSApp
class Vertex {
public char label; // label (e.g. 'A')
public boolean wasVisited;
// -------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// -------------------------
} // end class Vertex
// //////////////////////////////////////////////////////////////
class Link {
public Vertex vertex; // data item (key)
public Link next; // next link in list
// -------------------------
public Link(Vertex data) // constructor
{
this.vertex = data;
}
// -------------------------
public void displayLink() // display ourself
{
System.out.print(vertex.label);
}
} // end class Link
// //////////////////////////////////////////////////////////////
class LinkList {
public Link first; // ref to first link on list
public Link last;
// -------------------------
public LinkList(Vertex c) // constructor
{
Link newLink = new Link(c);
last = first = newLink; // no links on list yet
}
// -------------------------
public void insertFirst(Vertex c) { // make new link
Link newLink = new Link(c);
newLink.next = first; // it points to old first link
first = newLink; // now first points to this
}
// ==============================================================
// 编程作业 13.2
public void insertLast(Vertex c) { // make new link
Link newLink = new Link(c);
last.next = newLink; // now first points to this
last = newLink;
}
// ==============================================================
// 编程作业 13.2
public Link find() // find link with non-visited vertex
{ // (assumes non-empty list)
Link current = first.next; // start at 'first.next'
while (current != null && current.vertex.wasVisited) // while no match,
{
current = current.next; // go to next link
}
return current; // found it
}
// ==============================================================
// -------------------------
public void displayList() // display the list
{
Link current = first; // start at beginning of list
System.out.print("List (" + current.vertex.label + "): ");
current = current.next;
while (current != null) // until end of list,
{
current.displayLink(); // print data
current = current.next; // move to next link
}
System.out.println("");
}
// -------------------------
} // end class LinkList
// //////////////////////////////////////////////////////////////
// //////////////////////////////////////////////////////////////
class StackX {
private final int SIZE = 20;
private Vertex[] st;
private int top;
// ------------------------
public StackX() // constructor
{
st = new Vertex[SIZE]; // make array
top = -1;
}
// ------------------------
public void push(Vertex j) // put item on stack
{
st[++top] = j;
}
// ------------------------
public Vertex pop() // take item off stack
{
return st[top--];
}
// ------------------------
public Vertex peek() // peek at top of stack
{
return st[top];
}
// ------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1);
}
// ------------------------
} // end class StackX
// //////////////////////////////////////////////////////////////
class Graph1 {
// ============================================================
// 编程作业 13.2
// 这里只用了一个LinkList数组
// 每个LinkList的第一个节点Link表示当前节点
// 后面节点表示与前节点相邻接的节点
// 其实Link完全可以由Vertex代替，在Vertex里面添加一个域next
// 这个next指向与此Vertex相邻接的顶点
private final int MAX_VERTS = 20;
private LinkList adjList[]; // adjacency list
private int nVerts; // current number of vertices
private StackX theStack;
// ------------------------
public Graph1() // constructor
{
// adjacency matrix
adjList = new LinkList[MAX_VERTS];
nVerts = 0;
theStack = new StackX();
} // end constructor
// ------------------------
public void addVertex(char lab) {
Vertex newVertex = new Vertex(lab);
LinkList list = new LinkList(newVertex);
adjList[nVerts++] = list;
}
// ------------------------
public void addEdge(int start, int end) {
adjList[start].insertLast(adjList[end].first.vertex);
}
// ------------------------
public void displayVertex(Vertex v) {
System.out.print(v.label);
}
// ------------------------
// ============================================================
// 编程作业 13.2
public void dfs() // depth-first search
{ // begin at vertex 0
adjList[0].first.vertex.wasVisited = true; // mark it
displayVertex(adjList[0].first.vertex); // display it
theStack.push(adjList[0].first.vertex); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
Vertex v = getAdjUnvisitedVertex(theStack.peek());
if (v == null) // if no such vertex,
theStack.pop();
else // if it exists,
{
v.wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
// stack is empty, so we're done
for (int j = 0; j < nVerts; j++)
// reset flags
adjList[j].first.vertex.wasVisited = false;
} // end dfs
// ============================================================
// 编程作业 13.2
// returns an unvisited vertex adj to v
public Vertex getAdjUnvisitedVertex(Vertex v) {
int j = -1;
for (int i = 0; i < adjList.length; i++) {
if (adjList[i].first.vertex.label == v.label) {
j = i;
break;
}
}
Link link = adjList[j].find();
if (link != null) {
return adjList[j].find().vertex;
} else {
return null;
}
} // end getAdjUnvisitedVertex()
// ============================================================
} // end class Graph
// //////////////////////////////////////////////////////////////
public class DFSApp {
public static void main(String[] args) {
Graph1 theGraph = new Graph1();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
theGraph.addEdge(0, 5); // AF
System.out.print("Visits: ");
theGraph.dfs(); // depth-first search
System.out.println();
} // end main()
} // end class DFSApp
// //////////////////////////////////////////////////////////////
/*
13.3 修改dfs.java程序（清单13.1）显示有向图的连通性表，就像“有向图的连
通性”那节描述的一样。
*/
package chap13.pp3;
// dfs.java
// demonstrates depth-first search
// to run this program: C>java DFSApp
////////////////////////////////////////////////////////////////
class StackX {
private final int SIZE = 20;
private int[] st;
private int top;
// ------------------------
public StackX() // constructor
{
st = new int[SIZE]; // make array
top = -1;
}
// ------------------------
public void push(int j) // put item on stack
{
st[++top] = j;
}
// ------------------------
public int pop() // take item off stack
{
return st[top--];
}
// ------------------------
public int peek() // peek at top of stack
{
return st[top];
}
// ------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1);
}
// ------------------------
} // end class StackX
// //////////////////////////////////////////////////////////////
class Vertex {
public char label; // label (e.g. 'A')
public boolean wasVisited;
// ------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// ------------------------
} // end class Vertex
// //////////////////////////////////////////////////////////////
class Graph {
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private StackX theStack;
// ------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int y = 0; y < MAX_VERTS; y++)
// set adjacency
for (int x = 0; x < MAX_VERTS; x++)
// matrix to 0
adjMat[x][y] = 0;
theStack = new StackX();
} // end constructor
// ------------------------
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// ------------------------
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
// adjMat[end][start] = 1;
}
// ------------------------
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
// ------------------------
public void dfs() // depth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theStack.push(0); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
// stack is empty, so we're done
for (int j = 0; j < nVerts; j++)
// reset flags
vertexList[j].wasVisited = false;
} // end dfs
// ------------------------
// returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++)
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
return j;
return -1;
} // end getAdjUnvisitedVertex()
// ------------------------
// ============================================================
// 编程作业 13.3
// Connectivity 连通性
// 通过修改dfs()方法得来
public void getConnectivity() {
for (int i = 0; i < nVerts; i++) {
vertexList[i].wasVisited = true; // mark it
displayVertex(i); // display it
theStack.push(i); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
// stack is empty, so we're done
for (int j = 0; j < nVerts; j++)
// reset flags
vertexList[j].wasVisited = false;
System.out.println();
}
}
// ============================================================
} // end class Graph
// //////////////////////////////////////////////////////////////
public class DFSApp {
public static void main(String[] args) {
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
theGraph.addEdge(0, 5); // DE
System.out.println("连通性: ");
theGraph.getConnectivity();
} // end main()
} // end class DFSApp
// //////////////////////////////////////////////////////////////
/*
13.4 实现Warshall算法来找到一个图的传递闭包。可以从编程作业13.3题开始。
它有助于显示在算法的不同阶段显示邻接矩阵。
*/
package chap13.pp4;
// dfs.java
// demonstrates depth-first search
// to run this program: C>java DFSApp
////////////////////////////////////////////////////////////////
class StackX {
private final int SIZE = 20;
private int[] st;
private int top;
// ------------------------
public StackX() // constructor
{
st = new int[SIZE]; // make array
top = -1;
}
// ------------------------
public void push(int j) // put item on stack
{
st[++top] = j;
}
// ------------------------
public int pop() // take item off stack
{
return st[top--];
}
// ------------------------
public int peek() // peek at top of stack
{
return st[top];
}
// ------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1);
}
// ------------------------
} // end class StackX
// //////////////////////////////////////////////////////////////
class Vertex {
public char label; // label (e.g. 'A')
public boolean wasVisited;
// ------------------------
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
// ------------------------
} // end class Vertex
// //////////////////////////////////////////////////////////////
class Graph {
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // list of vertices
private int adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private StackX theStack;
// ------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int y = 0; y < MAX_VERTS; y++)
// set adjacency
for (int x = 0; x < MAX_VERTS; x++)
// matrix to 0
adjMat[x][y] = 0;
theStack = new StackX();
} // end constructor
// ------------------------
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// ------------------------
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
// adjMat[end][start] = 1;
}
// ------------------------
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
// ------------------------
public void dfs() // depth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theStack.push(0); // push it
while (!theStack.isEmpty()) // until stack empty,
{
// get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(theStack.peek());
if (v == -1) // if no such vertex,
theStack.pop();
else // if it exists,
{
vertexList[v].wasVisited = true; // mark it
displayVertex(v); // display it
theStack.push(v); // push it
}
} // end while
// stack is empty, so we're done
for (int j = 0; j < nVerts; j++)
// reset flags
vertexList[j].wasVisited = false;
} // end dfs
// ------------------------
// returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++)
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
return j;
return -1;
} // end getAdjUnvisitedVertex()
// ------------------------
// ============================================================
// 编程作业 13.4
// TransitiveClosure 传递闭包
// Warshall算法
public void doTransitiveClosure() {
for (int x = 0; x < adjMat.length; x++) { // 行
for (int y = 0; y < adjMat.length; y++) { // 列
if (adjMat[x][y] == 1) { // x -> y
for (int z = 0; z < adjMat.length; z++) {// 行
if (adjMat[z][x] == 1) { // z -> x
adjMat[z][y] = 1; // x -> y
}
}
}
}
}
}
// ============================================================
public void displayMat() {
for (int i = 0; i < nVerts; i++) {
for (int j = 0; j < nVerts; j++) {
System.out.print(adjMat[i][j] + " ");
}
System.out.println();
}
}
} // end class Graph
// //////////////////////////////////////////////////////////////
public class DFSApp {
public static void main(String[] args) {
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (start for dfs)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2
theGraph.addVertex('D'); // 3
theGraph.addVertex('E'); // 4
theGraph.addVertex('F'); // 5
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
theGraph.addEdge(0, 5); // AF
theGraph.displayMat();
theGraph.doTransitiveClosure();
System.out.println("生成传递闭包: ");
theGraph.displayMat();
} // end main()
} // end class DFSApp
// //////////////////////////////////////////////////////////////
/*
13.5 骑士旅行是一个古老而著名的象棋谜题。题目是在一个空的棋盘上移动一个
骑士，从一个方块到另一个，直到踏遍了棋盘的所有的方块。写一个程序，
用深度优先搜索解决这个问题。最好使棋盘的大小可变，这样可以在较小的
棋盘上解决这个问题。8*8的棋盘中，用个人电脑大概需要几年的时间解决
这个问题。5*5的棋盘只需要几分钟而已。
//骑士只能根据象棋的规则进行移动，要么横向跳动一格纵向跳动两格
//要么纵向跳动一格横向跳动两格。 例如， n=4，m=3 时，若骑士在格子(2;1)，
//则骑士只能移入下面格子：(1;3),(3;3) 或 (4;2)
*/
package chap13.pp5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//=================================================================
class StackX {
private final int SIZE = 200;
private Lattice[] st;
private int top;
// ------------------------
public StackX() // constructor
{
st = new Lattice[SIZE]; // make array
top = -1;
}
// ------------------------
public void push(Lattice j) // put item on stack
{
st[++top] = j;
}
// ------------------------
public Lattice pop() // take item off stack
{
return st[top--];
}
// ------------------------
public Lattice peek() // peek at top of stack
{
return st[top];
}
// ------------------------
public boolean isEmpty() // true if nothing on stack
{
return (top == -1);
}
// ------------------------
} // end class StackX
// =================================================================
// lattice 格子
// 棋格
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 < MAX_X
&& lattice.y < MAX_Y) {
return true;
}
return false;
}
// =================================================================
// lattice 给定的棋格
// f 开始遍历的方法
// 返回lattice的下一个未访问的后继棋格
public Lattice getNextUnVisitedLattice(int f, Lattice lattice) {
for (int i = f; i < direction.length; i++) {
Lattice temp = lattice.getNextLattice(i, direction[i]);
if (isValid(temp)) { // 在棋盘内
if (!chessBoard[temp.x][temp.y]) { // 没有访问
return temp;
}
}
}
return null;
}
// =================================================================
// 编程作业 13.5
// 骑士的旅行
// 过程：
// 首先任选一个棋格标记为已访问并加入栈
// 如果栈不为空-------(1)
// --找栈顶棋格的后继未访问棋格
// --如果找到，则后继未访问棋格标记为已访问，并入栈
// --如果未找到，则把栈顶元素退栈
// --如果所有棋格都已入栈，则骑士旅行完成，方法结束
// 循环进入(1)
// 如果栈为空
// 则未找到骑士旅行的路径，方法结束
public void knightTour() {
StackX path = new StackX(); // 存放已访问的棋格
path.push(new Lattice(-1, 0, 0)); // 从第(0,0)个棋格开始
number--;
chessBoard[0][0] = true;
// disPlayChessBoard();
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("success!找到骑士旅行的路径!");
return;
}
}
System.out.println("failure!找不到骑士旅行的路径!");
}
// =================================================================
// 显示骑士旅行路径
public void disPlayKnightTour() {
for (int i = 0; i < MAX_X; i++) { // 初始化棋盘
for (int k = 0; k < MAX_Y; k++) {
chessBoard[i][k] = false;
}
}
for (int i = 0; i < path.length; i++) { // 骑士每移动一步，打印一次棋盘
Lattice temp = path[i];
chessBoard[temp.x][temp.y] = true;
disPlayChessBoard();
}
}
// =================================================================
// 打印棋盘
public void disPlayChessBoard() {
System.out.print(" ");
for (int i = 0; i < MAX_Y; i++) {
System.out.print(" " + i);
}
System.out.println();
for (int i = 0; i < MAX_X; i++) {
System.out.print(" " + i);
for (int j = 0; j < MAX_Y; j++) {
if (chessBoard[i][j] == false) {
System.out.print(" □");
} else {
System.out.print(" ■");
}
}
System.out.println();
}
System.out.println();
}
// =================================================================
}
public class Knight {
public static void main(String[] args) throws IOException {
System.out.print("请输入棋盘的宽：");
int x = getInt();
System.out.print("请输入棋盘的高：");
int y = getInt();
Chess chess = new Chess(x, y);
// chess.disPlayChessBoard();
chess.knightTour();
}
// -------------------------
public static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------
public static int getInt() throws IOException {
String s = getString();
return Integer.parseInt(s);
}
// -------------------------
}