马踏棋盘算法详解
2021/6/18 22:33:57
本文主要是介绍马踏棋盘算法详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
马踏棋盘算法详解
说明
- 马踏棋盘是指在一个8 * 8的国际棋盘上,从某一位置开始,每次走一个日字,将所有的位置都走一遍
- 可以使用递归 + 回溯来解决,再加上贪心算法来优化
- 指定某种策略,因为从棋盘的某一位置开始走,它的下一步最多有8个选择,编写一个方法,将下一步能走的位置记录在集合中
- 创建一个Boolean数组记录当前位置是否走过,如果没有走过则可以走,否则不能
- 从开始的位置开始,遍历它的下一步可以走的位置的集合,如果当前位置没有走过,则从当前位置又重新开始走,开始判断下一次可以走的位置,如果走不通则回溯
- 直到所有的位置都访问过,并且走完相应的步数
- 在从集合中选择下一步时,优先选择下一步的下一步可选择的位置较少的位置,体现贪心的思想
- 源码见下
源码及分析
package algorithm.algorithm.horse; import java.awt.*; import java.util.ArrayList; import java.util.Comparator; /** * @author AIMX_INFO * @version 1.0 */ @SuppressWarnings("all") public class HorseChessBoard { //棋盘的列 public static int X; //棋盘的行 public static int Y; //判断当前位置是否走过 public static boolean[] visited; //判断是否完成 public static boolean finished; public static void main(String[] args) { X = 8; Y = 8; int row = 2; int col = 4; visited = new boolean[X * Y]; int[][] chessboard = new int[X][Y]; traversalChessBoard(chessboard, row - 1, col - 1, 1); show(chessboard); } //显示棋盘 public static void show(int[][] chessboard){ for (int[] rol : chessboard) { for (int step : rol) { System.out.print(step + "\t"); } System.out.println(); } } /** * @param chess 棋盘 * @param row 从棋盘的哪一行开始 * @param col 那一列 * @param step 表示走的第几步 */ public static void traversalChessBoard(int[][] chess, int row, int col, int step) { //设置当前位置是第几步 chess[row][col] = step; //设置当前位置为已经走过 visited[row * X + col] = true; //取出当前位置可以走的下一步的集合 ArrayList<Point> ps = next(new Point(col, row)); //使用贪心算法思想,优先走下一步选择较少的位置 ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { return next(o1).size() - next(o2).size(); } }); //然后遍历下一步所有可以走的点 while (!ps.isEmpty()) { Point p = ps.remove(0); if (!visited[p.y * X + p.x]) { traversalChessBoard(chess, p.y, p.x, step + 1); } } //当当前位置的下一个位置走不通时,判断是否走完,如果没有走完,将当前位置置为未走过 if (step < X * Y && !finished) { chess[row][col] = 0; visited[row * X + col] = false; } else { finished = true; } } /** * \ * * @param cur 当前位置点的坐标 * @return 返回从当前位置可以走的下一个位置的所有点的集合 */ public static ArrayList<Point> next(Point cur) { //创建集合保存可以走的点 ArrayList<Point> ps = new ArrayList<>(); //创建一个点 Point p = new Point(); if ((p.x = cur.x - 2) >= 0 && (p.y = cur.y - 1) >= 0) { ps.add(new Point(p)); } if ((p.x = cur.x - 1) >= 0 && (p.y = cur.y - 2) >= 0) { ps.add(new Point(p)); } if ((p.x = cur.x + 2) < X && (p.y = cur.y - 1) >= 0) { ps.add(new Point(p)); } if ((p.x = cur.x + 1) < X && (p.y = cur.y - 2) >= 0) { ps.add(new Point(p)); } if ((p.x = cur.x + 2) < X && (p.y = cur.y + 1) < Y) { ps.add(new Point(p)); } if ((p.x = cur.x + 1) < X && (p.y = cur.y + 2) < Y) { ps.add(new Point(p)); } if ((p.x = cur.x - 2) >= 0 && (p.y = cur.y + 1) < Y) { ps.add(new Point(p)); } if ((p.x = cur.x - 1) >= 0 && (p.y = cur.y + 2) < Y) { ps.add(new Point(p)); } return ps; } }
这篇关于马踏棋盘算法详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)