java數(shù)據(jù)結(jié)構(gòu)與算法之馬踏棋盤
本文實例為大家分享了java數(shù)據(jù)結(jié)構(gòu)與算法之馬踏棋盤的具體代碼,供大家參考,具體內(nèi)容如下
- 馬踏棋盤算法也被稱為騎士周游問題
- 將馬隨機放在過期象棋的8x8棋盤的某個方格中,馬按走棋規(guī)則進行移動,要求每個方格只進入一次,走遍棋盤上全部64個方格
騎士周游問題結(jié)局步驟和思路
1.創(chuàng)建棋盤chessBoard,是一個二維數(shù)組
2.將當前位置設(shè)置為已個訪問,然后根據(jù)當前位置,計算馬兒還能走那些位置,并放到一個集合中(ArrayList),最多8個位置
3.變量ArrayList存放的所有位置,看看哪個可以走通
4.判斷馬兒是否完成了騎士周游問題
注意:馬兒不同的走法,會得到不同的結(jié)果,效率也會有影響
代碼實現(xiàn)
public class HorseChessBoard { ?? ?private static int X; ?//棋盤的列數(shù) ?? ?private static int Y; ?//棋盤的行數(shù) ?? ? ?? ?//創(chuàng)建數(shù)組標記棋盤各個位置是否被訪問過 ?? ?private static boolean[] visited; ?? ?//使用一個屬性標記是否棋盤的所有位置都被訪問過,即是否成功 ?? ?private static boolean finish; ?//如果為true表示成功 ?? ? ?? ?public static void main(String[] args) { ?? ??? ?X = 8; ?? ??? ?Y = 8; ?? ??? ?int row = 1; ?? ??? ?int col = 1;? ?? ??? ?int[][] chessboard = ?new int[X][Y]; ?? ??? ?visited = new boolean[X * Y]; ?? ??? ? ?? ??? ?long start = System.currentTimeMillis(); ?? ??? ?traversalChessboard(chessboard, row-1, col-1, 1); ?? ??? ?long end = System.currentTimeMillis(); ?? ??? ?System.out.println(end - start); ?? ??? ? ?? ??? ?for (int[] rows : chessboard) { ?? ??? ??? ?for (int step : rows) { ?? ??? ??? ??? ?System.out.print(step + " ?"); ?? ??? ??? ?} ?? ??? ??? ?System.out.println(); ?? ??? ?} ?? ?} ?? ? ?? ?//其實周游問題 ?? ?public static void traversalChessboard(int[][] chessboard, int row, int col, int step) { ?? ??? ? ?? ??? ?if (finish) return; ?? ??? ?chessboard[row][col] = step; ?? ??? ?visited[row * X + col] = true; ?//標記該位置已經(jīng)訪問 ?? ??? ?//獲取當前位置可以走的下一個位置的集合 ?? ??? ?List<Point> ps = next(new Point(col, row)); ?? ??? ?sort(ps); ?? ??? ? ?? ??? ?//遍歷ps ?? ??? ?while (!ps.isEmpty()) { ?? ??? ??? ?Point p = ps.remove(0); ?//取出下一個可以走的位置 ?? ??? ??? ?//判斷該點是否已經(jīng)訪問過 ?? ??? ??? ?if (!visited[p.y * X + p.x]) { ?? ??? ??? ??? ?traversalChessboard(chessboard, p.y, p.x, step+1); ?? ??? ??? ?} ?? ??? ?} ?? ??? ? ?? ??? ?//1. 棋盤到目前位置任然未走完 ?? ??? ?//2. 棋盤處于一個回溯過程 ?? ??? ?if (step < X * Y && !finish) { ?? ??? ??? ?chessboard[row][col] = 0; ?? ??? ??? ?visited[row * X + col] = false; ?? ??? ?} else { ?? ??? ??? ?finish = true; ?? ??? ?} ?? ?} ?? ? ?? ?//根據(jù)當前這一步的所有的下一步的選擇位置進行非遞減排序 ?? ?public static void sort(List<Point> ps) { ?? ??? ?ps.sort(new Comparator<Point>() { ?? ??? ??? ?@Override ?? ??? ??? ?public int compare(Point o1, Point o2) { ?? ??? ??? ??? ?//獲取o1,o2下一步所有個數(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; ?? ??? ??? ??? ?} ?? ??? ??? ?} ?? ??? ?}); ?? ?} ?? ? ?? ?//Point:根據(jù)當前位置(point對象) ?? ?//根據(jù)當前位置,計算馬兒還能走那些位置,并放到一個集合中(ArrayList),最多8個位置 ?? ?public static List<Point> next(Point curPoint) { ?? ??? ?//創(chuàng)建list集合 ?? ??? ?List<Point> ps = new ArrayList<>(); ?? ??? ?//創(chuàng)建一個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; ?? ?} }
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
使用Spring的StopWatch實現(xiàn)代碼性能監(jiān)控的方法詳解
在開發(fā)過程中,偶爾還是需要分析代碼的執(zhí)行時間,Spring 框架提供了一個方便的工具類 StopWatch,本文將介紹 StopWatch 的基本用法,并通過示例演示如何在項目中使用 StopWatch 進行代碼性能監(jiān)控2023-12-12Hibernate+JDBC實現(xiàn)批量插入、更新及刪除的方法詳解
這篇文章主要介紹了Hibernate+JDBC實現(xiàn)批量插入、更新及刪除的方法,結(jié)合實例形式較為詳細的分析了Hibernate與JDBC針對數(shù)據(jù)庫的批量操作相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2017-11-11Spring?Data?JPA系列QueryByExampleExecutor使用詳解
這篇文章主要為大家介紹了Spring?Data?JPA系列QueryByExampleExecutor使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-09-09詳解ConcurrentHashMap如何保證線程安全及底層實現(xiàn)原理
這篇文章主要為大家介紹了ConcurrentHashMap如何保證線程安全及底層實現(xiàn)原理詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-05-05