马踏棋盘算法（java+没有贪心算法）-创新互联

import java.util.Arrays;

public class Test {public static final int LEFT_UP = 0;//左上
    public static final int UP_LEFT = 1;//上左
    public static final int UP_RIGHT = 2;//上右
    public static final int RIGHT_UP = 3;//右上
    public static final int RIGHT_DOWN = 4;//右下
    public static final int DOWN_RIGHT = 5;//下右
    public static final int DOWN_LEFT = 6;//下左
    public static final int LEFT_DOWN = 7;//左下
    public static int currentNum = 1;//马的步数本来就位1，因为出生地算一个
    public static int goalNum = 8;//寻找的目标数,如果goalNum为4，则目标数为16

    public static void main(String[] args) {long start = System.currentTimeMillis();
        for (int x = 0; x< goalNum; x++) {for (int y = 0; y< goalNum; y++) {int[] position = {x, y};//马儿的初始位置
                int[][] map = new int[goalNum][goalNum];//地图
                map[position[0]][position[1]] = 1;
                for (int direction = LEFT_UP; direction<= LEFT_DOWN; direction++) {if (move(direction, position, map)) {//如果递归成功
                        long end = System.currentTimeMillis();
                        System.out.println(String.format("总耗时为%d秒", (end - start) / 1000));
                        return;
                    }
                }
            }
        }
    }

    public static boolean judgePosition(int[] position, int[][] map) {//判断路况是否合法即每走完一步，落脚点必须在棋盘内，期盼的边界为   [0,0]-[3,3]，且棋盘当前位置不能重新踩
        return ((position[0] >= 0 && position[0]<= goalNum - 1) && (position[1] >= 0 && position[1]<= goalNum - 1)) && map[position[0]][position[1]] != 1;
    }

    //递归一次，currentNum就得+1
    public static boolean move(int direction, int[] position, int[][] map) {//移动
        if (currentNum == goalNum * goalNum) {//如果当前数量已经达到了递归的目标数，则返回true
            printMap(position, map);
            return true;
        } else {currentNum++;//当前数量+1
            int[] positionCopy = Arrays.copyOf(position, position.length);//一进入这个方法，就将position的值保存下来
            int[][] mapCopy = new int[goalNum][goalNum];
            for (int i = 0; i< goalNum; i++) {for (int j = 0; j< goalNum; j++) {mapCopy[i][j] = map[i][j];
                }
            }
            modifyPosition(direction, position);//修改位置
            if (!judgePosition(position, map)) {//如果修改的坐标不合法或者说原有地图此位置已经为1
                currentNum--;//当前数量-1
                restorePosition(direction, position);//将坐标进行还原
                return false;
            }
            map[position[0]][position[1]] = 1;
            for (int nextDirection = LEFT_UP; nextDirection<= LEFT_DOWN; nextDirection++) {if (move(nextDirection, position, map)) {//如果递归成功
                    printMap(positionCopy, mapCopy);
                    return true;
                }
            }
            map[position[0]][position[1]] = 0;
            restorePosition(direction, position);//将坐标进行还原
            currentNum--;//当前数量-1
            return false;
        }
    }

    public static void modifyPosition(int direction, int[] position) {//修改位置
        switch (direction) {case LEFT_UP:
                position[0] -= 1;
                position[1] -= 2;
                break;
            case UP_LEFT:
                position[0] -= 2;
                position[1] -= 1;
                break;
            case UP_RIGHT:
                position[0] -= 2;
                position[1] += 1;
                break;
            case RIGHT_UP:
                position[0] -= 1;
                position[1] += 2;
                break;
            case RIGHT_DOWN:
                position[0] += 1;
                position[1] += 2;
                break;
            case DOWN_RIGHT:
                position[0] += 2;
                position[1] += 1;
                break;
            case DOWN_LEFT:
                position[0] += 2;
                position[1] -= 1;
                break;
            case LEFT_DOWN:
                position[0] += 1;
                position[1] -= 2;
                break;
        }
    }

    public static void restorePosition(int direction, int[] position) {//还原位置
        switch (direction) {case LEFT_UP:
                position[0] += 1;
                position[1] += 2;
                break;
            case UP_LEFT:
                position[0] += 2;
                position[1] += 1;
                break;
            case UP_RIGHT:
                position[0] += 2;
                position[1] -= 1;
                break;
            case RIGHT_UP:
                position[0] += 1;
                position[1] -= 2;
                break;
            case RIGHT_DOWN:
                position[0] -= 1;
                position[1] -= 2;
                break;
            case DOWN_RIGHT:
                position[0] -= 2;
                position[1] -= 1;
                break;
            case DOWN_LEFT:
                position[0] -= 2;
                position[1] += 1;
                break;
            case LEFT_DOWN:
                position[0] -= 1;
                position[1] += 2;
                break;
        }
    }

    public static void printMap(int[] position, int[][] map) {for (int i = 0; i< goalNum; i++) {for (int j = 0; j< goalNum; j++) {System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println(Arrays.toString(position));
        System.out.println("=====================");
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧