马踏棋盘问题(贪心算法实现C++)

2024-08-31 03:32

本文主要是介绍马踏棋盘问题(贪心算法实现C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法实现流程:

步骤1初始化马的位置(结构体horse {x, y})

步骤2:确定马从当前点出发,可跳跃的附近8个点,以结构体Jump数组给出,但需判断当前给出的附近8个点是否曾经访问过,或者是否这8个点超出棋盘尺寸。

步骤3:跟据步骤2确定跳跃的点,分别计算可跳跃点的下下一步,可跳跃点的个数。并选出下下步可跳跃点数最少的点作为马下一步跳跃的点。(举例说明:马当前所在点坐标(4,4),下一步可跳跃点有(5,2),(6,3),且(5,2)下一步可跳跃点有3个,(6,3)下一步可跳跃点2个;3 > 2这个时候,选择下下一跳小的点进行跳跃,则马下一跳为(6,3))

流程图:

        

#pragma once
#include <iostream>
#include <math.h>
using namespace std;
#define SAFE_DELETE(x) if (x != NULL) {delete(x); x = NULL;}
#define SAFE_DELETE_ARR(x) if (x != NULL) {delete[](x); x = NULL;}
#define PRING_ARR(title, arr, n) {cout << title << " "; for (int i=0; i<n; i++) {cout << arr[i] << " ";} cout << endl;}#define INF 9999999typedef struct
{int x;int y;
}Location;typedef struct
{int delx;int dely;
}Jump;class HorseRun
{
private:int** altas;int N; //棋盘的宽Location horse; //马当前的位置
public:HorseRun(){N = 8;altas = new int* [N]();for (int j = 0; j < N; j++){altas[j] = new int[N]();memset(altas[j], 0, sizeof(int) * N);}//随机生成马的初始位置horse = { rand() % N, rand() % N };altas[horse.x][horse.y] = 1;cout << "马初始位置:" << "(" << horse.x << "," << horse.y << ")" << endl;Visit();}~HorseRun(){for (int i = 0; i < N; i++)SAFE_DELETE_ARR(altas[i]);SAFE_DELETE_ARR(altas);}inline void Visit(){Jump jump[8] = { {1,-2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2} };int max_visit = 63;int forward_x, forward_y, forward_xx, forward_yy, w_cnt, min_cnt, tmp_run_x, tmp_run_y;while (max_visit-- > 0){min_cnt = INF;//棋子可跳八个方位for (int i = 0; i < 8; i++){forward_x = horse.x + jump[i].delx;forward_y = horse.y + jump[i].dely;//判断这两个坐标是否有效if (forward_x < 0 || forward_x >= N || forward_y < 0 || forward_y >= N || altas[forward_x][forward_y] == 1)continue;w_cnt = 0;for (int j = 0; j < 8; j++){forward_xx = forward_x + jump[j].delx;forward_yy = forward_y + jump[j].dely;if (forward_xx < 0 || forward_xx >= N || forward_yy < 0 || forward_yy >= N || altas[forward_xx][forward_yy] == 1)continue;w_cnt++;}if (min_cnt > w_cnt){min_cnt = w_cnt;tmp_run_x = forward_x;tmp_run_y = forward_y;}}//棋子移动判断if (min_cnt == INF){cout << "没有找到可以移动的地方" << endl;break;}else{horse.x = tmp_run_x;horse.y = tmp_run_y;altas[tmp_run_x][tmp_run_y] = 1;cout <<"第"<< 63 - max_visit << "步," << "棋子当前移动到:" << "(" << tmp_run_x << ", " << tmp_run_y << ")" << endl;}}}
};#define  _CRT_SECURE_NO_WARNINGS true
#include "HorseRun.h"
int main()
{HorseRun app;return 0;
}

运行结果输出1-63步马行驶的具体路径信息:

中间还有很多输出省略。。。

 

这篇关于马踏棋盘问题(贪心算法实现C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1122767

相关文章

Linux下修改hostname的三种实现方式

《Linux下修改hostname的三种实现方式》:本文主要介绍Linux下修改hostname的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下修改ho编程stname三种方式方法1:修改配置文件方法2:hFvEWEostnamectl命

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Nginx实现前端灰度发布

《Nginx实现前端灰度发布》灰度发布是一种重要的策略,它允许我们在不影响所有用户的情况下,逐步推出新功能或更新,通过灰度发布,我们可以测试新版本的稳定性和性能,下面就来介绍一下前端灰度发布的使用,感... 目录前言一、基于权重的流量分配二、基于 Cookie 的分流三、基于请求头的分流四、基于请求参数的分

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

Python Excel实现自动添加编号

《PythonExcel实现自动添加编号》这篇文章主要为大家详细介绍了如何使用Python在Excel中实现自动添加编号效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍简单的说,就是在Excel中有一列h=会有重复

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod