马踏棋盘（从低效到高效）

2023-11-09 05:10
文章标签 高效 棋盘 低效 马踏

本文主要是介绍马踏棋盘（从低效到高效），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

将棋子“马”随机的放在国际象棋棋盘Board[8][8]的某个方格中，“马”按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上所有的64个方格。

题目要求

编写非递归程序，求出“马”的行走路线，并按求出的行走路线将数字1-64依次填入一个8x8的方阵并输出。

分析 x 1

一看题目说是8x8棋盘，要求走遍棋盘，首先想到的便是直接深搜即可，但是后面说到要求非递归程序，这也简单，自己把递归的那一部分
改为用栈来实现即可（马走棋盘肯定会遇到走不下去的情况，所以需要储存之前已经走过的点，而“悔棋”肯定是从当前这一步往之前返
回，所以是一个后进先出的结构——栈）。
定义
typedef struct _horse
{int x;  //横坐标int y;  //纵坐标int s;  //下一步的方向
}HORSE;
int chessboard[8][8];   //棋盘
int Next[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};  //方向
int cnt = 1;            //计数器
stack<HORSE> horse;
执行函数
bool judge(int a, int b)
{if(a < 0 || a > 7 || b < 0 || b > 7)    //边界return false;return true;
}void Horse(int x, int y)
{HORSE temp;int a,b;	//记录当前马位置附近的坐标int i = 0;chessboard[x][y] = cnt;	//标记当前起始位置已被访问 temp.x = x;	//记录当前马的位置temp.y = y;while(cnt < 64){for(; i < 8; i++){a = temp.x + Next[i][0];b = temp.y + Next[i][1];if(judge(a,b) && chessboard[a][b] == 0)     //判断{break;}}if(i < 8)	//能够访问当前马位置附近的日点{chessboard[a][b] = ++cnt;temp.s = i;horse.push(temp);memset(&temp, 0, sizeof(HORSE));temp.x = a;temp.y = b;i = 0;}else	//回溯{--cnt;chessboard[temp.x][temp.y] = 0;HORSE tt = horse.top();horse.pop();temp.x = tt.x;temp.y = tt.y;i = tt.s;++i;	//继续搜索从当前马位置访问的点的下一个点继续访问}}
}

完成后测试了一下，只有（0，0）可以跑出来，可见这种暴力的方式效率实在是太低…

分析 x 2

上面的暴力试探方式效率实在太低了，所以我们要优化一下代码。
把书继续往后翻，有提到将马的初始步入栈，计算其8个方向的权值，将其按升序排列，马从最小权值的点开始走，
无路可走时回溯（权值就是一个点下一步能走的点的总数）。
这是一种贪心的思想，那么既然是贪心，我们可不可以再贪心一些，每一步直接走权值最小的点，不再回溯，看能不能走完。
执行函数
void Horse(int x, int y)
{HORSE temp;int a,b;    //记录当前马位置附近的坐标chessboard[x][y] = cnt; //标记当前起始位置已被访问 temp.x = x; //记录当前马的位置temp.y = y;while(cnt < 64){int h_min = 8;      //权值最小的点int tx,ty,ti;       //记录权值最小的点的信息for(int i = 0; i < 8; i++){a = temp.x + Next[i][0];b = temp.y + Next[i][1];if(judge(a,b) && chessboard[a][b] == 0)     //判断{int step = steps(a,b);   //计算权值if(step < h_min)         //更新权值最小的点{h_min = step;    tx = a;ty = b;ti = i;}            }}//直接走权值最小的点chessboard[tx][ty] = ++cnt;temp.s = ti;//temp.step = h_min;horse.push(temp);memset(&temp, 0, sizeof(HORSE));temp.x = tx;temp.y = ty;}
}

这次测试了一下，效率大大的提高了，但是我们是“最”贪心的方法，所以我们要测试一下，看能不能从任意点出发都能走完棋盘。
经过测试有一个点不能走完棋盘，就是（2，4），也就是三行五列的点。

分析 x 3

好吧，既然只有一个点不能按照我们最贪心的方式走完，那么我们就只对这一个点特殊处理一下。
处理方式即就是分析2时所说的按权值大小排序，从最小的开始走。

最终版本

#include <iostream>
#include <stack>
#include <cstring>
#include <algorithm>using namespace std;/* 马踏棋盘 */typedef struct _horse
{int x;  //横坐标int y;  //纵坐标int s;  //下一步的方向int step;   //下一步的权值int flag;  //特殊点用
}HORSE;int chessboard[8][8];   //棋盘
int Next[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};  //方向
int cnt = 1;            //计数器
stack<HORSE> horse;//判别
bool judge(int a, int b)
{if(a < 0 || a > 7 || b < 0 || b > 7)    //边界return false;return true;
}//从小到大排序
bool cmp(HORSE& a, HORSE& b)
{return a.step < b.step;
}//计算权值
int steps(int a, int b)
{int sum = 0;for(int i = 0; i < 8; i++){int x = a + Next[i][0];int y = b + Next[i][1];if(judge(x,y) && chessboard[x][y] == 0)++sum;}return sum;
}//执行过程
void Horse(int x, int y)
{HORSE temp;int a,b;    //记录当前马位置附近的坐标chessboard[x][y] = cnt; //标记当前起始位置已被访问 temp.x = x; //记录当前马的位置temp.y = y;while(cnt < 64){int h_min = 8;      //权值最小的点int tx,ty,ti;       //记录权值最小的点的信息for(int i = 0; i < 8; i++){a = temp.x + Next[i][0];b = temp.y + Next[i][1];if(judge(a,b) && chessboard[a][b] == 0)     //判断{int step = steps(a,b);   //计算权值if(step < h_min)         //更新权值最小的点{h_min = step;    tx = a;ty = b;ti = i;}            }}//直接走权值最小的点chessboard[tx][ty] = ++cnt;temp.s = ti;//temp.step = h_min;horse.push(temp);memset(&temp, 0, sizeof(HORSE));temp.x = tx;temp.y = ty;}
}//特殊点执行过程（2，4）
void Horse_2(int x, int y)
{HORSE temp;HORSE horse_2[8];memset(horse_2, 0, sizeof(HORSE));int a,b;int flag = 0;   //记录该走那一个点了chessboard[x][y] = cnt;temp.x = x;temp.y = y;while(cnt < 64){int k = 0;for(int i = 0; i < 8; i++){a = temp.x + Next[i][0];b = temp.y + Next[i][1];if(judge(a,b) && chessboard[a][b] == 0)     //找出可走的点{int step = steps(a,b);horse_2[k].x = a;horse_2[k].y = b;horse_2[k].s = i;horse_2[k].step = step;++k;}}sort(horse_2, horse_2 + k, cmp);    //按权值从小到大排序for(int i = 0; i < k; i++)horse_2[i].flag = i;    if(k > 0 && flag < k)   //有路可走{chessboard[horse_2[flag].x][horse_2[flag].y] = ++cnt;temp.s = horse_2[flag].s;temp.step = horse_2[flag].step;temp.flag = horse_2[flag].flag;horse.push(temp);memset(&temp, 0, sizeof(HORSE));temp.x = horse_2[flag].x;temp.y = horse_2[flag].y;flag = 0;}else    //回溯{--cnt;chessboard[temp.x][temp.y] = 0;HORSE tt = horse.top();horse.pop();temp.x = tt.x;temp.y = tt.y;flag = tt.flag;++flag; //走下一个点}}
}//输出
void print()
{for(int i = 0; i < 8; i++){for(int j = 0; j < 8; j++)cout << chessboard[i][j] << ' ';cout << endl;}
}int main()
{int x,y;cout << "从那个点开始: ";cin >> x >> y;if(x == 2 && y == 4)Horse_2(x,y);elseHorse(x,y);print();return 0;
}

在这里插入图片描述

这篇关于马踏棋盘（从低效到高效）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/374137。

相关文章

高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

摘要 近日，万博智云推出了基于AWS的无代理跨云容灾解决方案，并与拉丁美洲，中东，亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础，将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合，为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日，万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频，介绍了
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
高效录音转文字：2024年四大工具精选！

高效录音转文字：2024年四大工具精选！

在快节奏的工作生活中，能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候，一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具！ 365在线转文字 直达链接：https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具，它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件，只
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
基于 YOLOv5 的积水检测系统：打造高效智能的智慧城市应用

基于 YOLOv5 的积水检测系统：打造高效智能的智慧城市应用

在城市发展中，积水问题日益严重，特别是在大雨过后，积水往往会影响交通甚至威胁人们的安全。通过现代计算机视觉技术，我们能够智能化地检测和识别积水区域，减少潜在危险。本文将介绍如何使用 YOLOv5 和 PyQt5 搭建一个积水检测系统，结合深度学习和直观的图形界面，为用户提供高效的解决方案。 源码地址： PyQt5+YoloV5 实现积水检测系统 预览： 项目背景
阅读更多...
MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

项目主页：https://tangyuan96.github.io/minigpt_3d_project_page/ 代码：https://github.com/TangYuan96/MiniGPT-3D 论文：https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA，被ACM MM2024接收，只拥有47.8M的可训练参数，在一张RTX
阅读更多...
利用命令模式构建高效的手游后端架构

利用命令模式构建高效的手游后端架构

在现代手游开发中，后端架构的设计对于支持高并发、快速迭代和复杂游戏逻辑至关重要。命令模式作为一种行为设计模式，可以有效地解耦请求的发起者与接收者，提升系统的可维护性和扩展性。本文将深入探讨如何利用命令模式构建一个强大且灵活的手游后端架构。 1. 命令模式的概念与优势 命令模式通过将请求封装为对象，使得请求的发起者和接收者之间的耦合度降低。这种模式的主要优势包括： 解耦请求发起者与处理者
阅读更多...
PDFQFZ高效定制：印章位置、大小随心所欲

PDFQFZ高效定制：印章位置、大小随心所欲

前言 在科技编织的快节奏时代，我们不仅追求速度，更追求质量，让每一分努力都转化为生活的甜蜜果实——正是在这样的背景下，一款名为PDFQFZ-PDF的实用软件应运而生，它以其独特的功能和高效的处理能力，在PDF文档处理领域脱颖而出。 它的开发，源自于对现代办公效率提升的迫切需求。在数字化办公日益普及的今天，PDF作为一种跨平台、不易被篡改的文档格式，被广泛应用于合同签署、报告提交、证书打印等各个
阅读更多...
excel翻译软件有哪些？如何高效提翻译？

excel翻译软件有哪些？如何高效提翻译？

你是否曾在面对满屏的英文Excel表格时感到头疼？项目报告、数据分析、财务报表... 当这些重要的信息被语言壁垒阻挡时，效率和理解度都会大打折扣。别担心，只需3分钟，我将带你轻松解锁excel翻译成中文的秘籍。 无论是职场新人还是老手，这一技巧都将是你的得力助手，让你在信息的海洋中畅游无阻。 方法一：使用同声传译王软件 同声传译王是一款专业的翻译软件，它支持多种语言翻译，可以excel
阅读更多...
《C++中的移动构造函数与移动赋值运算符：解锁高效编程的最佳实践》

《C++中的移动构造函数与移动赋值运算符：解锁高效编程的最佳实践》

在 C++的编程世界中，移动构造函数和移动赋值运算符是提升程序性能和效率的重要工具。理解并正确运用它们，可以让我们的代码更加高效、简洁和优雅。 一、引言 随着现代软件系统的日益复杂和对性能要求的不断提高，C++程序员需要不断探索新的技术和方法来优化代码。移动构造函数和移动赋值运算符的出现，为解决资源管理和性能优化问题提供了有力的手段。它们允许我们在不进行不必要的复制操作的情况下，高效地转移资源
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2