思路分析

代碼實現

package com.atguigu.horse;import java.awt.*; import java.util.ArrayList; import java.util.Comparator;public class HorseChessboard {private static int x;//棋盤的列數private static int y;//棋盤的行數//創建一個數組，標記棋盤的各個位置是否被訪問過private static boolean visited[];//使用一個屬性，標記是否棋盤的所有位置都被訪問過private static boolean finished;//如果為true表示成功public static void main(String[] args) {//測試騎士周游算法是否正確x=8;y=8;int row=1;//馬兒走的初始位置的行，從1開始編號int column=1;//馬兒初始位置的列，從1開始編號//創建棋盤int[][] chessboard=new int[x][y];visited=new boolean[x*y];//初始值都是false//測試一下耗時long start = System.currentTimeMillis();traversalChessboard(chessboard,row-1,column-1,1);long end = System.currentTimeMillis();System.out.println("共耗時："+(end-start)+"毫秒");//輸出棋盤的最后情況for(int[] rows:chessboard){for(int step:rows){System.out.print(step+"\t");}System.out.println();}}/*** 完成騎士周游問題的算法* @param chessboard 棋盤* @param row 馬兒當前的位置的行 從0開始* @param column 馬兒當前的位置的列 從0開始* @param step 是第幾部，初始位置就是第一步*/public static void traversalChessboard(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));//對ps進行排序，排序的規則就是對PS的所有的Point對象的下一步的位置的數目，進行非遞減排序sort(ps);//遍歷我們的pswhile (!ps.isEmpty()){Point p = ps.remove(0);//取出下一個可以走的位置//判斷該點是否已經訪問過if(!visited[p.y*x+p.x]){//說明環沒有訪問過traversalChessboard(chessboard,p.y,p.x,step+1);}}//判斷馬兒是否完成了任務，使用step和應該走的步數比較，//如果沒有達到數量，則表示沒有完成任務，將整個棋盤置0//說明：step<x*y成立的情況有兩種//1.棋盤到目前位置，仍然沒有走完//2.棋盤處于一個回溯過程if(step<x*y&&!finished){chessboard[row][column]=0;visited[row*x+column]=false;}else {finished=true;}}/*** 根據當前的(Point對象)，計算馬兒還能走哪些位置，并放入到一個集合中(ArrayList),最多有8個位置* @param curPoint* @return*/public static ArrayList<Point> next(Point curPoint){//創建一個ArrayListArrayList<Point> ps = new ArrayList<>();//創建一個PointPoint p1 = new Point();//表示馬兒可以走5的位置if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){ps.add(new Point(p1));}//判斷馬兒可以走6的位置if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){ps.add(new Point(p1));}//判斷馬兒可以走7的位置if((p1.x=curPoint.x+1)<x&&(p1.y=curPoint.y-2)>=0){ps.add(new Point(p1));}//判斷馬兒可以走0的位置if((p1.x=curPoint.x+2)<x&&(p1.y=curPoint.y-1)>=0){ps.add(new Point(p1));}//判斷馬兒可以走1的位置if((p1.x=curPoint.x+2)<x&&(p1.y=curPoint.y+1)<y){ps.add(new Point(p1));}//判斷馬兒可以走2的位置if((p1.x=curPoint.x+1)<x&&(p1.y=curPoint.y+2)<y){ps.add(new Point(p1));}//判斷馬兒可以走3的位置if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<y){ps.add(new Point(p1));}//判斷馬兒可以走4的位置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>() {@Overridepublic int compare(Point o1, Point o2) {//獲取到o1的下一步所有位置個數int count1 = next(o1).size();//獲取到o2的下一步所有位置個數int count2 = next(o2).size();return count1-count2;}});}} 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的马踏棋盘算法(骑士周游)+贪心优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。