package com.HorseChess;

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

public class HorseChess {
? ? private static int X;
? ? private static int Y;
? ? private static boolean visited[];
? ? private static boolean finished;

? ? public static void main(String[] args) {
? ? ? ? Scanner sc = new Scanner(System.in);
? ? ? ? System.out.println("請輸入行：");
? ? ? ? X = sc.nextInt();
? ? ? ? System.out.println("請輸入列：");
? ? ? ? Y = sc.nextInt();
? ? ? ? System.out.println("請輸入棋子所在行：");
? ? ? ? int row = sc.nextInt();
? ? ? ? System.out.println("請輸入棋子所在列：");
? ? ? ? int column = sc.nextInt();
? ? ? ? int [][] chessboard = new int[X][Y];
? ? ? ? visited = new boolean[X*Y];
? ? ? ? traverchess(chessboard,row-1,column-1,1);
? ? ? ? for(int[] rows : chessboard){
? ? ? ? ? ? for (int step : rows){
? ? ? ? ? ? ? ? System.out.print(step + "\t");
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println();
? ? ? ? }
? ? }

? ? public static void traverchess(int[][] chessboard,int row,int column,int step){
? ? ? ? chessboard[row][column] = step;
? ? ? ? visited[row * X+column] = true;
? ? ? ? ArrayList<Point> ps = next(new Point(column,row));
? ? ? ? sort(ps);
? ? ? ? while (!ps.isEmpty()){
? ? ? ? ? ? Point p = ps.remove(0);
? ? ? ? ? ? if(!visited[p.y*X+p.x]){
? ? ? ? ? ? ? ? traverchess(chessboard,p.y,p.x,step+1);
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? if(step<X*Y&&!finished){
? ? ? ? ? ? chessboard[row][column] = 0;
? ? ? ? ? ? visited[row * X + column] = false;
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? finished = true;
? ? ? ? }
? ? }
? ? //判斷當(dāng)前棋子下一個可以走的所有位置數(shù)組
? ? public static ArrayList<Point> next(Point curpoint){
? ? ? ? ArrayList<Point> ps = new ArrayList<Point>();
? ? ? ? Point p1 = new Point();
? ? ? ? if((p1.x = curpoint.x - 2)>=0&&(p1.y = curpoint.y - 1)>=0){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x - 1)>=0&&(p1.y = curpoint.y - 2)>=0){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x + 1)< X && (p1.y = curpoint.y - 2)>=0){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x + 2)< X && (p1.y = curpoint.y - 1)>=0){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x + 2)<X&&(p1.y = curpoint.y + 1)<Y){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x + 1)<X&&(p1.y = curpoint.y + 2)<Y){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x - 1)>=0&&(p1.y = curpoint.y + 2)<Y){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? if((p1.x = curpoint.x - 2)>=0&&(p1.y = curpoint.y + 1)<Y){
? ? ? ? ? ? ps.add(new Point(p1));
? ? ? ? }
? ? ? ? return ps;
? ? }

? ? //使用貪心算法提高算法運行速度
? ? public static void sort(ArrayList<Point> ps){
? ? ? ? ps.sort(new Comparator<Point>() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Point o1, Point o2) {
? ? ? ? ? ? ? ? int count1 = next(o1).size();
? ? ? ? ? ? ? ? int count2 = next(o2).size();
? ? ? ? ? ? ? ? if(count1<count2){
? ? ? ? ? ? ? ? ? ? return ?-1;
? ? ? ? ? ? ? ? }else if (count1 == count2){
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? return ?1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? });
? ? }
}