java-马踏棋盘
在8x8的国际棋盘上,按照马走日的规则,验证是否能够走遍棋盘。
1、创建棋盘 chessBoard,是一个二维数组。
2、将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走一步,就使用step+1。
3、遍历ArrayList中存放的所有位置,看看哪个可以走通,如果走通,就继续,走不通,就回溯。
4、判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0。
package com.horse;import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;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 = 8;Y = 8;int row = 1; //马儿初始位置的行,从1开始编号int column = 1; //马儿初始位置的列,从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 是第几步 ,初始位置就是第1步 */public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {chessboard[row][column] = step;//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36visited[row * X + column] = true; //标记该位置已经访问//获取当前位置可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column, row));//对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目,进行非递减排序sort(ps);//遍历 pswhile(!ps.isEmpty()) {Point p = ps.remove(0);//取出下一个可以走的位置//判断该点是否已经访问过if(!visited[p.y * X + p.x]) {//说明还没有访问过traversalChessboard(chessboard, p.y, p.x, step + 1);}}//判断马儿是否完成了任务,使用 step 和应该走的步数比较 , //如果没有达到数量,则表示没有完成任务,将整个棋盘置0//说明: 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) {//创建一个ArrayListArrayList<Point> ps = new ArrayList<Point>();//创建一个PointPoint 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;}//根据当前这个一步的所有的下一步的选择位置,进行非递减排序, 减少回溯的次数public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {// TODO Auto-generated method stub//获取到o1的下一步的所有位置个数int count1 = next(o1).size();//获取到o2的下一步的所有位置个数int count2 = next(o2).size();if(count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});}
}
相关文章:
java-马踏棋盘
在8x8的国际棋盘上,按照马走日的规则,验证是否能够走遍棋盘。 1、创建棋盘 chessBoard,是一个二维数组。 2、将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中&…...
系统架构设计师-软件架构设计(4)
目录 一、软件架构评估 1、敏感点 2、权衡点 3、风险点 4、非风险点 5、架构评估方法 5.1 基于调查问卷或检查表的方式 5.2 基于度量的方式 5.3 基于场景的方式 6、基于场景的评估方法 6.1 软件架构分析法(SAAM) 6.2 架构权衡分析法(ATAM&am…...
51单片机--AD/DA
AD/DA介绍 AD和DA是模拟信号和数字信号之间的转换过程。 AD,全称为模拟到数字(Analog-to-Digital),指的是将模拟信号转换为数字信号的过程。在AD转换中,模拟信号经过采样、量化和编码等步骤,被转换为离散的…...
网络安全-防御需知
目录 网络安全-防御 1.网络安全常识及术语 资产 漏洞 0day 1day 后门 exploit APT 2.什么会出现网络安全问题? 网络环境的开放性 协议栈自身的脆弱性 操作系统自身的漏洞 人为原因 客观原因 硬件原因 缓冲区溢出攻击 缓冲区溢出攻击原理 其他攻击…...
C#百万数据处理
C#百万数据处理 在我们经验的不断增长中不可避免的会遇到一些数据量很大操作也复杂的业务 这种情况我们如何取优化如何去处理呢?一般都要根据业务逻辑和背景去进行合理的改进。 文章目录 C#百万数据处理前言一、项目业务需求和开发背景项目开发背景数据量计算业务需…...
windows端口占用
1.查看当前端口被哪个进程占用了(进入到CMD中) netstat -ano|findstr "8990"输出结果为: TCP 127.0.0.1:8990 0.0.0.0:0 LISTENING 2700 我们发现8990端口被2700进程占用了 2.基于进程号找进程名称 tasklist|findstr "2700&qu…...
如何理解Diffusion
Diffusion算法可以有多个角度进行理解,不同的理解方式只是对目标函数进行了不同的解释。其主体思想是不变的,可以归纳为: 训练时通过图片逐步添加噪声,变为一个纯噪声。然后学习每一步的噪声。推理时给定一个随机噪声图片&#x…...
自然语言处理从入门到应用——LangChain:模型(Models)-[聊天模型(Chat Models):使用少量示例和响应流式传输]
分类目录:《自然语言处理从入门到应用》总目录 使用少量示例 本部分的内容介绍了如何在聊天模型(Chat Models)中使用少量示例。关于如何最好地进行少量示例提示尚未形成明确的共识。因此,我们尚未固定任何关于此的抽象概念&#…...
Java在线OJ项目(三)、前后端交互API模块
Java在线OJ项目(三)、前后端交互API模块 1. 客户端向服务器请求所有题目 或者 单个题目前端获取所有题目获取一个题目 后端 2. 后端读取前端提交的代码,进行编译运行,返回结果前端提交代码后端处理 1. 客户端向服务器请求所有题目…...
项目——负载均衡在线OJ
目录 项目介绍开发环境所用技术项目宏观结构编写思路1. 编写compile_server1.1 编译模块编写1.2 运行功能1.3compile_runner 编译与运行1.4 编写compile_server.cpp调用compile_run模块,形成网络服务 2. 编写基于MVC的oj_server2.1 oj_server.cpp的编写2.2 oj_model…...
idea连接远程服务器上传war包文件
idea连接远程服务器&上传war包 文章目录 idea连接远程服务器&上传war包1. 连接服务器2.上传war包 1. 连接服务器 选择Tools -> Start SSH Session 添加配置 连接成功 2.上传war包 Tools -> Deployment -> Browse Remote Host 点击右侧标签,点击&…...
使用PyGWalker可视化分析表格型数据
大家好,可以想象一下在Jupyter Notebook中拥有大量数据,想要对其进行分析和可视化。PyGWalker就像一个神奇的工具,能让这项工作变得超级简单。它能获取用户的数据,并将其转化为一种特殊的表格,可以与之交互,…...
Visual C++中的虚函数和纯虚函数(以外观设计模式为例)
我是荔园微风,作为一名在IT界整整25年的老兵,今天来说说Visual C中的虚函数和纯虚函数。该系列帖子全部使用我本人自创的对比学习法。也就是当C学不下去的时候,就用JAVA实现同样的代码,然后再用对比的方法把C学会。 直接说虚函数…...
电子元器件选型与实战应用—01 电阻选型
大家好, 我是记得诚。 这是《电子元器件选型与实战应用》专栏的第一篇文章,今天的主角是电阻,在每一个电子产品中,都少不了电阻的身影,其重要性不言而喻。 文章目录 1. 入门知识1.1 基础1.2 常用品牌1.3 电阻的种类2. 贴片电阻标识2.1 三位数标注法2.2 四位数标注法2.3 小…...
javascript 模板引擎
使用场景 在实际开发中,一般都是使用动态请求数据来更新页面,服务器端通常返回json格式的数据,正常操作是我们手动的去拼装HTML,但麻烦且容易出错,因此出现了一些用模版生成HTML的的框架叫js模板引擎如:jq…...
【数据结构】带头+双向+循环链表(DList)(增、删、查、改)详解
一、带头双向循环链表的定义和结构 1、定义 带头双向循环链表,有一个数据域和两个指针域。一个是前驱指针,指向其前一个节点;一个是后继指针,指向其后一个节点。 // 定义双向链表的节点 typedef struct ListNode {LTDataType dat…...
接口自动化测试平台
下载了大神的EasyTest项目demo修改了下<https://testerhome.com/topics/12648 原地址>。也有看另一位大神的HttpRunnerManager<https://github.com/HttpRunner/HttpRunnerManager 原地址>,由于水平有限,感觉有点复杂~~~ 【整整200集】超超超…...
【物联网】微信小程序接入阿里云物联网平台
微信小程序接入阿里云物联网平台 一 阿里云平台端 1.登录阿里云 阿里云物联网平台 点击进入公共实例,之前没有的点进去申请 2.点击产品,创建产品 3.产品名称自定义,按项目选择类型,节点类型选择之恋设备,联网方式W…...
PKG内容查看工具:Suspicious Package for Mac安装教程
Suspicious Package Mac版是一款Mac平台上的查看 PKG 程序包内信息的应用,Suspicious Package Mac版支持查看全部包内全部文件,比如需要运行的脚本,开发者,来源等等。 suspicious package mac使用简单,只需在选择pkg安…...
第16节:R语言医学分析实例:肺切除手术的Apriori关联规则分析
关联规则 肺切除手术的Apriori关联规则分析。 分析的目的是确定患有肺癌并需要接受肺切除术的患者的共病症状。 了解哪些症状是共病的可以帮助改善患者护理和药物处方。 分析类型是关联规则学习,通过探索变量之间的关联或频繁项集,尝试在大型数据集中找到见解和隐藏关系(H…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
