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