八数码(bfs做法)非常详细,适合新手服用

题目描述: 

在一个 3×3 的网格中,1∼8这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如:

1 2 3
x 4 6
7 5 8

在游戏过程中,可以把 x 与其上、下、左、右四个方向之一的数字交换(如果存在)。

我们的目的是通过交换,使得网格变为如下排列(称为正确排列):

1 2 3
4 5 6
7 8 x

例如,示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下:

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行,将 3×3 的初始网格描绘出来。

例如,如果初始网格如下所示:

1 2 3 
x 4 6 
7 5 8 

则输入为:1 2 3 x 4 6 7 5 8

输出格式

输出占一行,包含一个整数,表示最少交换次数。

如果不存在解决方案,则输出 −1。

输入样例:

2 3 4 1 5 x 7 6 8

输出样例

19

思路: 

由于此题解法宽搜算法,所以我们可以把这样的一种

这样的一种情况看成一个点,从这个一点分散下去一个点有很多种情况,进行分层

如下图:

 此图来源于acwing题解中的一位大佬所画,由于每个边的权值是1(也就是距离),所以我们可以利用宽搜天生就带有性质,求出最短的路径。


那么这里我们可以看出来这种3*3的矩阵状态很难表示出来? 

所以我们才用字符串的形式进行存储,例如:

我们都知道写bfs的时候都是用队列存储,所以我们就可以用队列去存储这个字符串


再来思考如何去存储当前状态下的距离呢? 

我们可以使用C++下的unordered_map<string,int>,哈希表去存储当前字符串下的距离值是多少,然后通过最终我们想要的字符串和变换中的字符串进行比较,最后输出距离。


如何判断字符串能变成哪种状态呢? 

那么就需要用上面我们说的状态转换,先把一个字符串转换成3*3的矩阵,利用枚举当前x能移动的上下左右四个点,就可以做出变换,然后再变回字符串。

这里的难点就是一个一维数组如何变成二维数组,二维数组,如何去变回一维数组

下面一个小技巧希望大家牢记~

通用公式:

一维坐标映射到二维 -> (k / n, k % n )
二维映射一维 -> x * n + y


 AC代码:

#include<iostream>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<cstring>using namespace std;//宽搜,求最短路
int bfs(string start)
{//记录要求最终字符串样式string end = "12345678x";queue<string> q;//队列存储字符串unordered_map<string,int> d;//哈希表存储当前字符串下的对应值(距离)q.push(start);//进队d[start] = 0;//第一个距离初始化为0while(q.size()){//取出队首元素auto t = q.front();q.pop();//删除//取出当前字符串形式下的距离值int distance = d[t];//如果等于我们想要的值,那么直接返回距离输出结果if(t == end) return distance;//找出x在一维数组下的下标是多少int k = t.find('x');//状态转化,变成3*3矩阵下的下标int x = k / 3, y = k % 3;//上下左右偏移量int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};//枚举x上下左右四个点的偏移量for(int i=0;i<4;i++){//记录信的坐标点(3*3矩阵下)int a = x + dx[i],b = y + dy[i];//判断新坐标是否越界if(a >= 0 && a < 3 && b >= 0 && b < 3){//状态转化,变回一维数组下的字符串swap(t[k],t[a*3 + b]);//如果哈希表中没有,那么就当前距离+1if(!d.count(t)){d[t] = distance + 1;q.push(t);//新字符串进队}//恢复现场,变回字符串,因为变换一次还有3个位置还没换呢swap(t[k],t[a*3+b]);}}}return -1;//找不到就输出-1
}int main()
{string start;for(int i=0;i<9;i++){char c;cin >> c;start += c;}cout << bfs(start) << endl;return 0;
}

欢迎不会的小伙伴留言~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/297746.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

4.4C++

1 #include <iostream> #include <cmath> using namespace std; class A{ private:int a;// 判断一个数是否为质数bool isP(int num) {if (num<2) return false;for (int i2;i<sqrt(num);i) {if (num % i 0) {return false;}}return true;} public:// 构造…

51单片机入门_江协科技_19~20_OB记录的笔记

19. 串口通讯 19.1. 串口介绍&#xff1a; •串口是一种应用十分广泛的通讯接口&#xff0c;串口成本低、容易使用、通信线路简单&#xff0c;可实现两个设备的互相通信。 •单片机的串口可以使单片机与单片机、单片机与电脑、单片机与各式各样的模块互相通信&#xff0c;极大的…

Rust---复合数据类型之字符串与切片(2)

目录 字符串操作删除 (Delete)连接 (Concatenate) 字符串转义 前情回顾: Rust—复合数据类型之字符串&#xff08;1&#xff09; 字符串操作 删除 (Delete) 删除方法仅适用于 String 类型&#xff0c;分别是&#xff1a; pop()&#xff0c;remove()&#xff0c;truncate()&a…

无人售货奶柜:开启便捷生活的新篇章

无人售货奶柜&#xff1a;开启便捷生活的新篇章 在这个快节奏的现代生活中&#xff0c;科技的革新不仅为我们带来了前所未有的便利&#xff0c;更在不经意间改变着我们的日常。其中&#xff0c;无人售货技术的出现&#xff0c;尤其是无人售货奶柜&#xff0c;已经成为我们生活…

2024最新版Android studio安装入门教程(非常详细)

目录 JDK安装与配置 一、下载JDK 二、JDK安装 三、JDK的环境配置 四、JDK的配置验证 Android studio安装 Android studio连接手机真机调试&#xff08;以华为鸿蒙为例&#xff09; 一、新建一个android项目 二、进入项目面板 三、配置Android Studio 四、安装手机驱…

CentOS7安装MySQL8.0.28(持续)

第一步 &#xff1a;下载mysql MySQL https://www.mysql.com/

51单片机入门之独立按键

目录 1.按键简介 2.独立按键控制LED亮灭 3.独立按键控制LED移位 1.按键简介 在生活中&#xff0c;我们常常会见到各种按键&#xff0c;我们的开发板上也有按键&#xff0c;就在左下角有四个按键&#xff0c;我们把它们叫做独立按键。 独立按键的原理比较简单&…

10 款最佳 Mac 数据恢复软件,在为时已晚之前值得尝试

查看 10 年适用于 Mac 的 2024 款最佳免费数据恢复软件&#xff0c;可在大多数在线搜索中找到。精选列表将帮助您做出明智的决定并节省您的时间和精力。 10 款最佳 Mac 数据恢复软件 很明显&#xff0c;您此后将面临数据丢失事件。理所当然地&#xff0c;您期待一款可靠、与您…

【MATLAB源码-第30期】基于matlab的内边界边缘检测算法。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 在计算机视觉领域&#xff0c;图像分割&#xff08;segmentation&#xff09;指的是将数字图像细分为多个图像子区域&#xff08;像素的集合&#xff09;&#xff08;也被称作超像素&#xff09;的过程。图像分割的目的是简化…

SAP HCM 多成本中心薪酬过账标准程序解读

SAP HCM薪酬过账会涉及到CO对象&#xff0c;CO对象主要是成本中心、WBS、内部订单、订单等&#xff0c;成本中心有多个维护地方0001信息类型0027信息类型等&#xff0c;那么成本中心多个地方维护&#xff0c;优先级是如何&#xff0c;0027>1018>0001,也就是说人身上的优先…

Mysql故障和优化

一、MySQL故障 二、MySQL优化 1.硬件优化&#xff1a; 2.数据库设计与规划 1.提前估计数据量&#xff0c;使用什么存储引擎 2.数据库服务器专机专用&#xff0c;避免额外的服务可能导致的性能下降和不稳定性 3.增加多台服务器&#xff0c;以达到稳定、高效的效果。主从同步、…

http模块 设置资源类型(mime类型)

虽然浏览器自带websocket功能它会根据响应回来的内容自动去判断资源类型&#xff0c;但是我们加上了mime类型判断代码会更加规范些 一、mime类型概念&#xff1a; 媒体类型是一种标准&#xff0c;它用来表示文档。文件、字节流的性质和格式。HTTP服务可以设置响应头Content-T…

金三银四面试题(十四):Java基础问题(5)

这部分面试题多用于面试的热身运动&#xff0c;对很多找实习和准备毕业找工作的小伙伴至关重要。 避免序列化 可以使用transient 关键字修饰不想进行序列化的变量。 transient 关键字的作用是&#xff1a;阻止实例中那些用此关键字修饰的变量序列化&#xff1b;当对象被反序列…

【Linux】error: Failed to initialize NSS library

【Linux】error: Failed to initialize NSS library 原因&#xff1a;卸载了sqlite [rootnode1 ~]# rpm -qa|grep sql sqlite-3.7.17-8.el7.x86_64 rpm -e --nodeps sqlite-3.7.17-8.el7.x86_64 百度搜索 sqlite-3.7.17-8.el7.x86_64 下载此rpm包 cd /usr/local/download …

阿里云弹性计算通用算力型u1实例性能评测,性价比高

阿里云服务器u1是通用算力型云服务器&#xff0c;CPU采用2.5 GHz主频的Intel(R) Xeon(R) Platinum处理器&#xff0c;ECS通用算力型u1云服务器不适用于游戏和高频交易等需要极致性能的应用场景及对业务性能一致性有强诉求的应用场景(比如业务HA场景主备机需要性能一致)&#xf…

Web实例_报表开发01-基于HTML进行报表呈现

Web实例_报表开发01-基于HTML进行报表呈现 报表开发是一种在利用了软件的基础上, 针对不同类型的报表, 进行开放的工作。 而以报表的方式, 将相关的内容、数值呈现出来的话, 则会起到更好的概况作用。 再加上, 报表开发工作是依托于计算机来完成的, 因此在效率、完整性等方面…

职场口才提升之道

职场口才提升之道 在职场中&#xff0c;口才的重要性不言而喻。无论是与同事沟通协作&#xff0c;还是向上级汇报工作&#xff0c;亦或是与客户洽谈业务&#xff0c;都需要具备良好的口才能力。一个出色的职场人&#xff0c;除了拥有扎实的专业技能外&#xff0c;还应具备出色…

探索----------------阿里云

目录 一、阿里云四大件 1、云服务器ECS 2、云数据库RDS 3、负载均衡SLB 4、对象存储OSS 5、其他的云计算产品 1&#xff09;内容分发网络CDN 2&#xff09;专有网络 VPC 二、linux发行版本 三、你平时对系统会怎么优化&#xff08;五大负载&#xff09; 1、cpu 使用率…

在project模式下自定义Implementation Strategies

Implementation Settings定义了默认选项&#xff0c;当要定义新的implementation runs时会使用这些选项&#xff0c;选项的值可以在Vivado IDE中进行配置。 图1展示了“Settings”对话框中的“implementation runs”对话框。要从Vivado IDE打开此对话框&#xff0c;请从主菜单中…

Pygame基础8-碰撞

Collisions 在Pygame中&#xff0c;我们使用矩形来移动物体&#xff0c;并且用矩形检测碰撞。 colliderect检测两个矩形是否碰撞&#xff0c;但是没法确定碰撞的方向。 Rect1.colliderect(Rect2) # collision -> return Ture # else -> return Falsecollidepoint可以…