欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

java數(shù)據(jù)結(jié)構(gòu)與算法之馬踏棋盤

 更新時(shí)間:2022年02月15日 08:33:45   作者:Nobody A  
這篇文章主要為大家詳細(xì)介紹了java數(shù)據(jù)結(jié)構(gòu)與算法之馬踏棋盤,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

本文實(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)文章

最新評論