数据结构--5.2马踏棋盘算法(骑士周游问题)
题目渊源:
马踏棋盘问题(又称骑士周游问题或骑士漫游问题)是算法设计的经典问题之一。
题目要求:
国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。
#include <stdio.h>
#include <time.h>#define X 8
#define Y 8int chess[X][Y];//找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x,int *y,int count)
{switch(count){case 0:if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0){*y+=2;*y-=1;return 1;}break;case 1:if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 ){*x+=2;*y+=1;return 1;}break;case 2:if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 ){*x=*x+1;*y=*y-2;return 1;}break;case 3:if(*x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0){*x = *x+1;*y= *y+2;return 1;}break;case 4:if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0){*x= *x-2;*y= *y+1;return 1;}break;case 5:if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 ){*x= *x-2;*y = *y+1;return 1;}break;case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0){*x = *x - 1;*y = *y - 2;return 1;}break;case 7:if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0){*x = *x -1;*y = *y +2;return 1;}break;default:break;} return 0;
} void print()
{int i,j;for(i=0;i<X;i++){for(j=0;j<Y;j++){printf("%2d\t",chess[i][j]);}printf("\n");}printf("\n");
}//深度优先遍历棋盘
//(x,y)为位置坐标
//tag是标记变量
int TravelChessBoard(int x,int y,int tag)
{int x1= x,y1=y,count =0,flag =0;chess[x][y] = tag;if(x*Y == tag){//打印棋盘print();return 1; }//找到马的下一个可走的坐标(x1,y1)flag = nextxy(&x1,&y1,count);while(0==flag && count<7){count++;}while(flag){if(TravelChessBoard(x1,y1,tag+1)){return 1;}//出现意外,找到马的下一步可走坐标(x1,y1) x1=x;y1=y;count++;flag = nextxy(&x1,&y1,count);while(0==flag && count < 7){count++;flag = nextxy(&x1,&y1,count);}} if(0 == flag){chess[x][y] =0;} return 0;
} int main()
{int i,j;clock_t start,finish;start = clock();for(i=0;i<X;i++){for(j=0;j<Y;j++){chess[i][j]=0;}}if(TravelChessBoard(2,0,1)){printf("抱歉,马踏棋盘失败!\n");}finish = clock();printf("\n本次计算一共耗时:%f秒\n\n",(double)(finish - start)/CLOCKS_PER_SEC);return 0;
}
相关文章:
数据结构--5.2马踏棋盘算法(骑士周游问题)
题目渊源: 马踏棋盘问题(又称骑士周游问题或骑士漫游问题)是算法设计的经典问题之一。 题目要求: 国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。…...
如何使用CSS实现一个响应式图片幻灯片(Responsive Image Slider)效果?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 响应式图片幻灯片⭐ HTML结构⭐ CSS样式⭐ JavaScript交互⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个…...
Linux学习之lvm删除
umount /mnt/logicvolumntest卸载挂载。 lvremove /dev/vgname/my_lv可以删除逻辑卷,其中vgname是指定逻辑卷所在的卷组名称,my_lv是逻辑卷的名称。 注意:使用lvremove命令会永久删除逻辑卷和其中的数据,因此请在使用之前进行适当…...
bazel介绍以及其发展历史
简介 Bazel Google开源的,是一款与 Make、Maven 和 Gradle 类似的开源构建和测试工具。 它使用人类可读的高级构建语言。Bazel 支持多种语言的项目,可为多个平台构建输出。Bazel支持任意大小的构建目标,并支持跨多个代码库和大量用户的大型代…...
固定资产管理分析怎么写?
对企业内的固定资产进行全面的统计和分析,包括设备、装修、维修等方面的信息,有助于企业进行资产管理和风险控制。 通过该软件,用户可以实现对资产的跟踪和管理,如实时监测设备的使用情况,提高设备利用率和维护效率…...
【项目源码】一套基于springboot+Uniapp框架开发的智慧医院3D人体导诊系统源码
智慧医院3D人体导诊系统源码 开发语言:java 开发工具:IDEA 前端框架:Uniapp 后端框架:springboot 数 据 库:mysql 移 动 端:微信小程序、H5 “智慧导诊”以人工智能手段为依托,为…...
可能的二分法 -- 二分图判定【DFS、BFS分别实现】
886. 可能的二分法 class PossibleBipartition:"""可能的二分法「其实考察的就是二分图的判定」用dfs和bfs 两种方法分别实现https://leetcode.cn/problems/possible-bipartition/"""def __init__(self):self.success Trueself.color []self.…...
六级翻译备考
classical 经典的 Chinese literature 中国文学 朝代dynasty 统治 rule 社会稳定 steady society 治理有序 orderly governance 伟大的greatest 时代 times或者periods 被人们描绘成人类历史上伴随着治理有序,社会稳定的最伟大的时代之一 more and more越来越多 …...
Vue框架--Vue中的数据绑定
Vue中有两种数据绑定的方式 1.单向数据绑定(v-band):数据只能够从data流向页面 2.双向数据绑定(v-model):数据不仅仅能够从data流向页面,也可以从页面流向data。 备注: 1.双向绑定一般都应用在表单类元素上。(如:input、select等有value属性值的标签上) 2.…...
Unity——热更新浅析
热更新的思想从本质上来讲,要考虑一些问题。例如,一个完整的游戏最多可以有多大比例的资源通过网络加载?能否让尽可能多的资源通过网络加载? 通过网络加载有很多好处,不仅可以极大减小安装包的体积,而且有…...
IMPLEMENT_DYNCREATE的分析
一、介绍 IMPLEMENT_DYNCREATE 是一个宏(macro),通常与DECLARE_DYNCREATE宏一起在MFC框架中使用。它的作用是为一个派生自 CObject 的MFC类提供运行时类型信息(RTTI)和对象的动态创建支持。 具体来说,IMP…...
Java实现根据短连接获取1688商品详情数据,1688淘口令接口,1688API接口封装方法
要通过1688的API获取商品详情数据,您可以使用1688开放平台提供的接口来实现。以下是一种使用Java编程语言实现的示例,展示如何通过1688开放平台API获取商品详情属性数据接口: 首先,确保您已注册成为1688开放平台的开发者…...
ABAP FICO 凭证替代 凭证校验
凭证校验 1.T-CODE--->GGX2--->GBLR-->ZRGGBR000 2.将程序RGGBR000 复制为ZRGGBR000 3.GGB0--》财务会计--》凭证抬头或者行项目维护检验规则 4.OB28 维护特定的公司代码和调用点和确认,活动等级设置为1 5.GGB4-->激活校验 凭证替代 1.T-CODE--->GG…...
项目验收有哪些流程?
验收流程 科技计划项目验收/课题验收测试服务的被测对象是国家重大专项、科研课题的软件成果物,可以是一个模块、软件或系统等,也可以是软件套件或软件原型等。测试范围主要来源于课题的合同书/可行吧报告/申报书中的技术指标要求。所出具的科技项目验收…...
C++,类的继承
一、继承的基本概念 继承使得C能够从已有的类派生出新的类,而派生类继承了原有类的特征,包括方法。被继承者称为父类或基类,继承者称为子类或派生类。 继承的目的: 实现代码的重用性建立父类和子类之间的联系在实现多态的时候&a…...
作业33333333
一、正向解析 在开启DNS服务之前先将防火墙关闭。 systemctl stop firewalld.service 开启DNS服务,需要开启端先进行安装主软件,以及配置包管理软件 配置包管理软件一般会跟随主软件一起安装,如果没有手动安装一次就可以了。 安装完成之后&…...
Spring Cloud--从零开始搭建微服务基础环境【二】
😀前言 本篇博文是关于Spring Cloud–从零开始搭建微服务基础环境【二】,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到大家,…...
算法工程题(中序遍历)
* 题意说明: * 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 * * 示例 1: * 输入:root [1,null,2,3] * 输出:[1,3,2] * * 示例 2: * 输入:root [] * 输出:[] * *…...
jsch网页版ssh
使用依赖 implementation com.jcraft:jsch:0.1.55Server端代码 import com.jcraft.jsch.Channel; import com.jcraft.jsch.JSch; import com.jcraft.jsch.Session; import java.io.InputStream; import java.io.OutputStream; import java.util.concurrent.TimeUnit; import o…...
教程i.MX8MPlus开发板SPI转CAN操作
飞凌嵌入式OKMX8MP-C核心板有两路原生CAN总线,但用户在开发产品时可能需要用到更多的CAN,这该如何解决呢?今天小编将为大家介绍一种SPI转CAN的方法,供各位工程师小伙伴参考。 说明 OKMX8MP-C核心板有两路原生的SPI总线,…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
