《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 verticesprivate int adjMat[][]; // adjacency matrixprivate int nVerts; // current number of verticesprivate Queue theQueue;// ------------------------public Graph() // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int j = 0; j < MAX_VERTS; j++)// set adjacencyfor (int k = 0; k < MAX_VERTS; k++)// matrix to 0adjMat[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.1public void mst() // breadth-first search{ // begin at vertex 0vertexList[0].wasVisited = true; // mark it// displayVertex(0); // display ittheQueue.insert(0); // insert at tailint v2;while (!theQueue.isEmpty()) // until queue empty,{int v1 = theQueue.remove(); // remove vertex at head// until it has no unvisited neighborswhile ((v2 = getAdjUnvisitedVertex(v1)) != -1) { // get one,vertexList[v2].wasVisited = true; // mark itdisplayVertex(v1);displayVertex(v2); // display itSystem.out.print(" ");theQueue.insert(v2); // insert it} // end while} // end while(queue not empty)// queue is empty, so we're donefor (int j = 0; j < nVerts; j++)// reset flagsvertexList[j].wasVisited = false;} // end bfs()// -------------------------// ===============================================================// returns an unvisited vertex adj to vpublic 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'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addEdge(0, 1); // ABtheGraph.addEdge(0, 2); // ACtheGraph.addEdge(0, 3); // ADtheGraph.addEdge(0, 4); // AEtheGraph.addEdge(1, 2); // BCtheGraph.addEdge(1, 3); // BDtheGraph.addEdge(1, 4); // BEtheGraph.addEdge(2, 3); // CDtheGraph.addEdge(2, 4); // CEtheGraph.addEdge(3, 4); // DESystem.out.print("Minimum spanning tree: ");theGraph.mst(); // minimum spanning treeSystem.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 DFSAppclass 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 listpublic 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 linkLink newLink = new Link(c);newLink.next = first; // it points to old first linkfirst = newLink; // now first points to this}// ==============================================================// 编程作业 13.2public void insertLast(Vertex c) { // make new linkLink newLink = new Link(c);last.next = newLink; // now first points to thislast = newLink;}// ==============================================================// 编程作业 13.2public 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 listSystem.out.print("List (" + current.vertex.label + "): ");current = current.next;while (current != null) // until end of list,{current.displayLink(); // print datacurrent = 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 arraytop = -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 listprivate int nVerts; // current number of verticesprivate StackX theStack;// ------------------------public Graph1() // constructor{// adjacency matrixadjList = 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.2public void dfs() // depth-first search{ // begin at vertex 0adjList[0].first.vertex.wasVisited = true; // mark itdisplayVertex(adjList[0].first.vertex); // display ittheStack.push(adjList[0].first.vertex); // push itwhile (!theStack.isEmpty()) // until stack empty,{// get an unvisited vertex adjacent to stack topVertex v = getAdjUnvisitedVertex(theStack.peek());if (v == null) // if no such vertex,theStack.pop();else // if it exists,{v.wasVisited = true; // mark itdisplayVertex(v); // display ittheStack.push(v); // push it}} // end while// stack is empty, so we're donefor (int j = 0; j < nVerts; j++)// reset flagsadjList[j].first.vertex.wasVisited = false;} // end dfs// ============================================================// 编程作业 13.2// returns an unvisited vertex adj to vpublic 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'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addVertex('F'); // 5theGraph.addEdge(0, 1); // ABtheGraph.addEdge(1, 2); // BCtheGraph.addEdge(0, 3); // ADtheGraph.addEdge(3, 4); // DEtheGraph.addEdge(0, 5); // AFSystem.out.print("Visits: ");theGraph.dfs(); // depth-first searchSystem.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 arraytop = -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 verticesprivate int adjMat[][]; // adjacency matrixprivate int nVerts; // current number of verticesprivate StackX theStack;// ------------------------public Graph() // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int y = 0; y < MAX_VERTS; y++)// set adjacencyfor (int x = 0; x < MAX_VERTS; x++)// matrix to 0adjMat[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 0vertexList[0].wasVisited = true; // mark itdisplayVertex(0); // display ittheStack.push(0); // push itwhile (!theStack.isEmpty()) // until stack empty,{// get an unvisited vertex adjacent to stack topint v = getAdjUnvisitedVertex(theStack.peek());if (v == -1) // if no such vertex,theStack.pop();else // if it exists,{vertexList[v].wasVisited = true; // mark itdisplayVertex(v); // display ittheStack.push(v); // push it}} // end while// stack is empty, so we're donefor (int j = 0; j < nVerts; j++)// reset flagsvertexList[j].wasVisited = false;} // end dfs// ------------------------// returns an unvisited vertex adj to vpublic 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 itdisplayVertex(i); // display ittheStack.push(i); // push itwhile (!theStack.isEmpty()) // until stack empty,{// get an unvisited vertex adjacent to stack topint v = getAdjUnvisitedVertex(theStack.peek());if (v == -1) // if no such vertex,theStack.pop();else // if it exists,{vertexList[v].wasVisited = true; // mark itdisplayVertex(v); // display ittheStack.push(v); // push it}} // end while// stack is empty, so we're donefor (int j = 0; j < nVerts; j++)// reset flagsvertexList[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'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addVertex('F'); // 5theGraph.addEdge(0, 1); // ABtheGraph.addEdge(1, 2); // BCtheGraph.addEdge(0, 3); // ADtheGraph.addEdge(3, 4); // DEtheGraph.addEdge(0, 5); // DESystem.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 arraytop = -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 verticesprivate int adjMat[][]; // adjacency matrixprivate int nVerts; // current number of verticesprivate StackX theStack;// ------------------------public Graph() // constructor{vertexList = new Vertex[MAX_VERTS];// adjacency matrixadjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for (int y = 0; y < MAX_VERTS; y++)// set adjacencyfor (int x = 0; x < MAX_VERTS; x++)// matrix to 0adjMat[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 0vertexList[0].wasVisited = true; // mark itdisplayVertex(0); // display ittheStack.push(0); // push itwhile (!theStack.isEmpty()) // until stack empty,{// get an unvisited vertex adjacent to stack topint v = getAdjUnvisitedVertex(theStack.peek());if (v == -1) // if no such vertex,theStack.pop();else // if it exists,{vertexList[v].wasVisited = true; // mark itdisplayVertex(v); // display ittheStack.push(v); // push it}} // end while// stack is empty, so we're donefor (int j = 0; j < nVerts; j++)// reset flagsvertexList[j].wasVisited = false;} // end dfs// ------------------------// returns an unvisited vertex adj to vpublic 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 -> yfor (int z = 0; z < adjMat.length; z++) {// 行if (adjMat[z][x] == 1) { // z -> xadjMat[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'); // 1theGraph.addVertex('C'); // 2theGraph.addVertex('D'); // 3theGraph.addVertex('E'); // 4theGraph.addVertex('F'); // 5theGraph.addEdge(0, 1); // ABtheGraph.addEdge(1, 2); // BCtheGraph.addEdge(0, 3); // ADtheGraph.addEdge(3, 4); // DEtheGraph.addEdge(0, 5); // AFtheGraph.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 arraytop = -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);}// -------------------------}