骑士周游算法
2023-02-26 12:27:29 时间
马踏棋盘游戏代码实现
package com.wxit.horse; import java.awt.*; import java.util.ArrayList; /** * @Author wj **/ 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) { System.out.println("开始测试骑士周游算法"); //测试骑士周游算法是否正确 X = 6; Y = 6; int row = 2;//马儿初始位置的行,从1开始编号 int column = 4; //马儿初始位置的列,从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 while (!ps.isEmpty()){ Point p = ps.remove(0);//取出下一个还可以走的位置 //判断该点是否已经访问过 if (!visited[p.y * X + p.x]){//说明还没有访问过 traversalChessboard(chessboard,p.y,p.x,step + 1); } } //判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示内有完成任务,将整个棋盘置零 //说明:step < X * Y成立的情况有两种 //1.棋盘到目前位置,仍然没有走完 //2.棋盘处于一个回溯的过程 if (step < X * Y && !finished){ chessboard[row][column] = 0; visited[row * X + column] = false; } else { finished = true; } } /** * 功能:根据当前位置(Point对象),计算马儿还能走那些位置(Point),并放入到一个集合中(ArrayList),最多有8个位置 * @param curPoint * @return */ public static ArrayList<Point> next(Point curPoint){ //创建一个ArrayList ArrayList<Point> ps = new ArrayList<>(); //创建一个point Point 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; } }
你还在原价购买阿里云、腾讯云、华为云、天翼云产品?那就亏大啦!现在申请成为四大品牌云厂商VIP用户,可以3折优惠价购买云服务器等云产品,并且可享四大云服务商产品终身VIP优惠价,还等什么?赶紧点击下面对应链接免费申请VIP客户吧:
相关文章
- 观远数据荣膺Gartner2022中国分析平台Cool Vendor
- 完整指南:使用 VirtualBox 在 Windows 上安装 Ubuntu
- 32 图 | 手摸手 Spring Cloud Gateway + JWT 实现登录认证
- 如何从边缘分析中推动业务价值
- EndeavourOS:你对完美的 Arch 发行版的搜寻到此为止
- 谈谈如何跨越数据架构的漩涡
- 在 Linux 上用 zram 替代传统交换空间
- 这才是真正的数据分析项目,而不是爬表
- Linux 中相对比较小众的命令:gunzip
- 程序员积累的编程知识十年后有多少变得没用?
- 文字间的战斗与其救世主 Unicode
- 简单的单例模式,Go版本的实现你写对了吗?
- 微软 OneNote Windows 11 预览版新增支持左侧垂直导航,不支持 Windows 10
- 阿里终面:说说OAuth2.0 与 单点登录的区别?
- 微软延长 Windows Server 2012 和 R2 上的 Edge 浏览器支持,至 2023 年 10 月
- 伙计,Go项目怎么使用枚举?
- 一款好用的 Go 调用链可视化工具
- Windows 11 隐藏功能:无需介质直接通过 Windows Update 更新重装系统
- 安全运行 Linux 服务器的初学者指南
- 供应链技术如何解决供应链中断和员工倦怠问题