Java代码实现利用栈解决骑士游历问题,并打印出路径坐标,实例化
时间: 2024-05-02 12:17:00 浏览: 10
以下是Java代码实现利用栈解决骑士游历问题,并打印出路径坐标,实例化的示例:
```
import java.util.Stack;
public class KnightTour {
private static final int BOARD_SIZE = 8;
private static final int[] ROW_MOVES = {2, 1, -1, -2, -2, -1, 1, 2};
private static final int[] COL_MOVES = {1, 2, 2, 1, -1, -2, -2, -1};
private int[][] board;
private Stack<String> path;
public KnightTour() {
board = new int[BOARD_SIZE][BOARD_SIZE];
path = new Stack<>();
}
public void solve() {
int moveCount = 1;
int row = 0;
int col = 0;
board[row][col] = moveCount;
path.push(row + "," + col);
while (moveCount < BOARD_SIZE * BOARD_SIZE) {
int[] nextMove = getNextMove(row, col);
if (nextMove == null) {
String lastMove = path.pop();
String[] lastMoveArr = lastMove.split(",");
row = Integer.parseInt(lastMoveArr[0]);
col = Integer.parseInt(lastMoveArr[1]);
board[row][col] = 0;
moveCount--;
} else {
row = nextMove[0];
col = nextMove[1];
board[row][col] = ++moveCount;
path.push(row + "," + col);
}
}
printPath();
}
private int[] getNextMove(int row, int col) {
for (int i = 0; i < ROW_MOVES.length; i++) {
int nextRow = row + ROW_MOVES[i];
int nextCol = col + COL_MOVES[i];
if (isValidMove(nextRow, nextCol)) {
return new int[]{nextRow, nextCol};
}
}
return null;
}
private boolean isValidMove(int row, int col) {
if (row < 0 || row >= BOARD_SIZE) {
return false;
}
if (col < 0 || col >= BOARD_SIZE) {
return false;
}
if (board[row][col] != 0) {
return false;
}
return true;
}
private void printPath() {
while (!path.isEmpty()) {
System.out.println(path.pop());
}
}
public static void main(String[] args) {
KnightTour tour = new KnightTour();
tour.solve();
}
}
```
在这个示例中,我们创建了一个KnightTour类来解决骑士游历问题。在构造函数中,我们初始化了一个8x8的棋盘,以及一个路径的栈。在solve方法中,我们通过迭代来尝试每一个可能的移动,直到棋盘被完全填满。getNextMove方法用来获取下一个可行的移动,isValidMove方法用来判断当前移动是否合法,printPath方法用来打印路径的坐标。最后在main方法中,我们实例化KnightTour类,并调用solve方法来解决问题。