package com.young.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author Shaw_Young
 * @date 2020/6/27 14:08
 */
public class HorseChessBoard {

    private static int X;// 棋盤的列數(shù)
    private static int Y;// 棋盤的行數(shù)
    // 創(chuàng)建一個(gè)數(shù)組,標(biāo)記棋盤的各個(gè)位置是否被訪問過
    private static boolean visited[];
    // 使用一個(gè)屬性,標(biāo)記是否棋盤的所有位置都被訪問
    private static boolean finished;// 如果為true,表示成功

    public static void main(String[] args) {
        System.out.println("騎士周游算法,開始運(yùn)行~~");
        // 測(cè)試其實(shí)周游算法是否正確
        X = 8;
        Y = 8;
        int row = 1;// 馬兒初始位置的行,從1開始編號(hào)
        int column = 1;// 馬兒初始位置的列,從1開始編號(hào)
        // 創(chuàng)建棋盤
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];// 初始值都是false
        // 測(cè)試一下耗時(shí)
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗時(shí): " + (end - start) + " 毫秒");
        //輸出棋盤的最后情況
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成騎士周游問題的算法
     *
     * @param chessboard 棋盤
     * @param row        馬兒當(dāng)前的位置的行,從0開始
     * @param column     馬兒當(dāng)前的位置的列,從0開始
     * @param step       是第幾步,初始位置就是第1步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        visited[row * X + column] = true;//標(biāo)記該位置已經(jīng)訪問
        // 獲取當(dāng)前位置可以走的下一個(gè)位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        // 對(duì)ps進(jìn)行排序,排序的規(guī)則就是對(duì)ps的所有的Point對(duì)象的下一步的位置的數(shù)目,進(jìn)行非遞減排序
        sort(ps);
        // 遍歷ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);//取出下一個(gè)可以走的位置
            // 判斷該點(diǎn)是否已經(jīng)訪問過
            if (!visited[p.y * X + p.x]) {//說明還沒有訪問過
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        // 判斷馬兒是否完成了任務(wù),使用step和應(yīng)該走的步數(shù)比較,如果沒有達(dá)到數(shù)量,則表示沒有完成任務(wù),將整個(gè)棋盤置0
        // 說明: step < X * Y 成立的情況有兩種
        // 1.棋盤到目前位置,仍然沒有走完
        // 2.棋盤處于一個(gè)回溯過程
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    /**
     * 功能: 根據(jù)當(dāng)前位置(Point對(duì)象),計(jì)算馬兒還能走哪些位置(Point),并放入到一個(gè)集合中(ArrayList),最多有8個(gè)位置
     *
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint) {
        // 創(chuàng)建一個(gè)ArrayList
        ArrayList<Point> ps = new ArrayList<>();
        // 創(chuàng)建一個(gè)Point
        Point p1 = new Point();
        // 表示馬兒可以走5這個(gè)位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走6這個(gè)位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走7這個(gè)位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走0這個(gè)位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走1這個(gè)位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走2這個(gè)位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走3這個(gè)位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        // 判斷馬兒可以走4這個(gè)位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根據(jù)當(dāng)前這個(gè)異步的所有的下一步的選擇位置,進(jìn)行非遞減排序,減少回溯的次數(shù)
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 獲取到o1的下一步的所有位置個(gè)數(shù)
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }

}