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…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
