Java代码实现利用栈解决骑士游历问题,并打印出路径坐标,实例化
时间: 2024-05-06 16:15:12 浏览: 7
以下是使用Java实现的骑士游历问题的栈解决方案:
```java
import java.util.*;
public class KnightTour {
private static final int BOARD_SIZE = 8;
private static final int[][] MOVES = {
{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
{1, -2}, {1, 2}, {2, -1}, {2, 1}
};
private static final int VISITED = -1;
private int[][] board;
private int[] start;
private Stack<int[]> stack;
public KnightTour(int[] start) {
this.start = start;
board = new int[BOARD_SIZE][BOARD_SIZE];
stack = new Stack<>();
}
public void solve() {
stack.push(start);
while (!stack.empty()) {
int[] current = stack.pop();
int row = current[0];
int col = current[1];
if (board[row][col] != VISITED) {
board[row][col] = VISITED;
if (isComplete()) {
printSolution();
return;
}
for (int[] move : MOVES) {
int nextRow = row + move[0];
int nextCol = col + move[1];
if (isValid(nextRow, nextCol)) {
stack.push(new int[]{nextRow, nextCol});
}
}
}
}
}
private boolean isValid(int row, int col) {
return row >= 0 && col >= 0 && row < BOARD_SIZE && col < BOARD_SIZE && board[row][col] != VISITED;
}
private boolean isComplete() {
for (int[] row : board) {
for (int square : row) {
if (square != VISITED) {
return false;
}
}
}
return true;
}
private void printSolution() {
System.out.println("Solution:");
for (int[] row : board) {
for (int square : row) {
System.out.print(square + "\t");
}
System.out.println();
}
}
public static void main(String[] args) {
int[] start = {0, 0};
KnightTour tour = new KnightTour(start);
tour.solve();
}
}
```
在这个实现中,我们使用了一个二维数组来表示棋盘,初始值都为0,已经访问过的位置标记为-1。我们使用一个栈来保存骑士的位置,每次从栈中取出一个位置,检查它是否已经访问过,如果没有,将其标记为已访问,检查是否已经访问完所有的位置,如果是,则打印解决方案并返回。否则,遍历所有可能的移动,将未访问过的下一个位置入栈。在这个实现中,我们没有直接使用递归,而是使用了栈来保存状态,从而实现了迭代的解决方案。