其实周游就是说马在一个棋盘上以走斜日的方式走棋盘,不能走已经走过的,需要将这个棋盘走完,最后一步回归原点,不过我的这个没有回归原点,如果需要回归我的这个算法也只需要判断以下即可
1.判断当前是否已经到达终点
2.如果不是,列举出当前马可以走的八个方位
3.尝试第一个方位
4.如果第一个方位可以走,就回到第一步,进入下一个循环
5.如果不可以便回到2尝试下一步,知道尝试完八个方位
public class HorseChessBoardTest {
public static void main(String[] args) {
HorseChessBoard horseChessBoard = new HorseChessBoard(8);
horseChessBoard.showChessBoard();
System.out.println();
System.out.println(horseChessBoard.goChessBoard(2,4));
horseChessBoard.showChessBoard();
}
}
class HorseChessBoard{
private int count; //需要走的总步数
private int step; //当前已经走的步数,根据这个和总部书判断是否已经完成所有步数
private int row; //行数
private int col; //列数,与行数相等,只是为了好分辨
private int[][] chess; //棋盘,0代表未走的,数字代表是走的第几步
//马站在一个位置可以踏的方向有八个,只需要用马的走遍和里面的每一个小数组相加即可,便于遍历
private int[][] direction = {{-2,-1},{-1,-2},{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1}};
//初始化工作
public HorseChessBoard(int chess) {
this.chess = new int[chess][chess];
col = row = chess;
count = chess*chess;
step = 1;
}
public boolean goChessBoard(int x,int y){
if(step == count && chess[x][y] == 0){//判断是否为最后一步,并且当前这一步是否合法,如果条件成立,代表走完
chess[x][y] = step;
return true;
}
boolean flag = false;
for (int[] ints : direction) {//循环遍历八个方向
//判断当前位置是否合法,以及下一步是否合法
if(x > -1 && x < col && y > -1 && y < row && x + ints[0] > -1 && x + ints[0] < col && y + ints[1] > -1 && y + ints[1] < row && chess[x][y] == 0){
chess[x][y] = step;
step++;
flag = goChessBoard(x + ints[0],y + ints[1]);//递归调用走下一步,并且返回结果
if(!flag){//如果上一步不能走通进行回溯
chess[x][y] = 0;
step--;
}else { //否则返回真
return true;
}
}
}
return flag;
}
public void showChessBoard(){ //显示棋盘
for (int[] ints : chess) {
for (int anInt : ints) {
System.out.print( anInt+ "\t");
}
System.out.println();
}
}
}