洛谷 P1379:八数码难题 ← BFS+unordered_map(哈希表)

 【题目来源】
https://www.luogu.com.cn/problem/P1379

【题目描述】
在 3×3 的棋盘上,摆有八个棋子,每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格,空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为 123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

【输入格式】
输入初始状态,一行九个数字,空格用 0 表示。

【输出格式】
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

【输入样例】
283104765

【输出样例】
4

【样例解释】

图中标有 0 的是空格。绿色格子是空格所在位置,橙色格子是下一步可以移动到空格的位置。如图所示,用四步可以达到目标状态。
并且可以证明,不存在更优的策略。

【算法分析】
unordered_map(哈希表):

https://cplusplus.com/reference/unordered_map/unordered_map/
https://cplusplus.com/reference/unordered_map/unordered_map/count/

【算法代码】

#include <bits/stdc++.h>
using namespace std;int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};string ans="123804765";int bfs(string s) {unordered_map<string, int> dis;dis[s]=0;queue<string> q;q.push(s);while(q.size()) {string t=q.front();q.pop();if(t==ans) return dis[t];int d=dis[t];int k=t.find('0');int x=k/3,y=k%3;for(int i=0; i<4; i++) {int tx=x+dx[i],ty=y+dy[i];if(tx>= 0 && tx<3 && ty>=0 && ty<3) {swap(t[k],t[tx*3+ty]);if(!dis.count(t)) {q.push(t);dis[t]=d+1;}swap(t[k],t[tx*3+ty]);}}}return -1;
}int main() {string s;cin>>s;cout<<bfs(s);
}/*
in:283104765
out:4
*/

 


【参考文献】
https://www.cnblogs.com/DM11/p/17001294.html
https://www.acwing.com/blog/content/5209/
https://www.cnblogs.com/sherluoke/p/15048778.html
https://blog.csdn.net/hnjzsyjyj/article/details/134756634
https://www.cnblogs.com/zufezzt/p/5659276.html
https://zhuanlan.zhihu.com/p/643917734
https://blog.csdn.net/Archerrrrr/article/details/110375815
https://blog.csdn.net/qq_60236552/article/details/119039352




 

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

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

相关文章

PTA结构体经典编程题

目录 第一题&#xff1a;计算平均成绩 第二题&#xff1a;平面向量加法 第三题&#xff1a;查找书籍 第四题&#xff1a;通讯录排序 第五题&#xff1a;计算职工工资 第一题&#xff1a;计算平均成绩 思路&#xff1a;看到一个学生的基本信息&#xff0c;所以定义一个结构…

Golang 原生Rpc Server实现

Golang 原生Rpc Server实现 引言源码解析服务端数据结构服务注册请求处理 客户端数据结构建立连接请求调用 延伸异步调用定制服务名采用TPC协议建立连接自定义编码格式自定义服务器 参考 引言 本文我们来看看golang原生rpc库的实现 , 首先来看一下golang rpc库的demo案例: 服…

AI创作ChatGPT源码+AI绘画(Midjourney绘画)+DALL-E3文生图+思维导图生成

一、AI创作系统 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI…

etlbox.3.1.0 for NET 轻量级 ETL数据集成库 Crack

适用于 .NET 的轻量级 ETL&#xff08;提取、转换、加载&#xff09;工具箱和数据集成库 高度可定制 厌倦了使用几乎不可能实现复杂需求的用户界面&#xff1f;使用 ETLBox&#xff0c;可以轻松编写适合您独特需求的代码。插入您自己的逻辑或修改现有行为以满足您的特定要求。 …

打造个性化github主页 一

文章目录 概述创建仓库静态美化GitHub 统计信息卡仓库 GitHub 额外图钉仓库 热门语言卡仓库 GitHub 资料奖杯仓库 GitHub 活动统计图仓库 打字特效添加中文网站统计仓库 总结 概述 github作为全球最大的代码托管平台&#xff0c;作为程序员都多多少少&#xff0c;都使用过他。…

盘点25个Html游戏Game源码网页爱好者不容错过

盘点25个Html游戏Game源码网页爱好者不容错过 学习知识费力气&#xff0c;收集整理更不易。 知识付费甚欢喜&#xff0c;为咱码农谋福利。 下载链接&#xff1a;https://pan.baidu.com/s/1lSNLjWB4xMuLV8m_kDtczw?pwd6666 提取码&#xff1a;6666 项目名称 21点游戏 H5…

随手写了个博客多平台发布脚本:Python自动发布文章到Wordpress

​ 引言 作为一名技术博主&#xff0c;提高博客发布效率是我们始终追求的目标。在这篇文章中&#xff0c;我将分享一个基于Python的脚本&#xff0c;能够实现博客多平台发布&#xff0c;具体来说&#xff0c;是自动发布文章到WordPress。通过这个简单而高效的脚本&#xff0c…

CSS 选择器优先级,!important 也会被覆盖?

目录 1&#xff0c;重要性2&#xff0c;专用性3&#xff0c;源代码顺序 CSS 属性值的计算过程中。其中第2步层叠冲突只是简单说明了下&#xff0c;这篇文章来详细介绍。 层叠冲突更广泛的被称为 CSS选择器优先级计算。 为什么叫层叠冲突&#xff0c;可以理解为 CSS 是 Cascadi…

JavaSE基础50题:7. 写一个方法返回参数二进制中1的个数(3种方法!)

文章目录 概述方法1方法2方法3 概述 返回参数中二进制中1的个数。 如&#xff1a; 15(十进制) —— 0000 1111(二进制) —— 4个1 ①我们把二进制的数字的每一位都&1&#xff0c;其中&#xff1a;1&11 、0&10 ②用无符号右移&#xff08;>>>&#xff09;来…

C++作业2

自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c; 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() 代码&#xff1a…

在PyCharm中运行OpenCV

一、安装Anaconda配置python环境 这里选用清华大学开源软件镜像站&#xff1a;anaconda | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 下载的速度更快。 点击下载链接&#xff1a;Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsin…

excel对号怎么打

对号无论是老师批改作业&#xff0c;还是在标注某些数据的时候都会用到&#xff0c;但这个符号在键盘上是没有的&#xff0c;那么excel对号怎么打出来呢&#xff0c;其实只要使用插入符号功能就可以了。 excel对号怎么打&#xff1a; 第一步&#xff0c;选中想要打出对号的单…

【探索Linux】—— 强大的命令行工具 P.19(多线程 | 线程的概念 | 线程控制 | 分离线程)

阅读导航 引言一、 Linux线程概念1. 什么是线程2. 线程的概念3. 线程与进程的区别4. 线程异常 二、Linux线程控制1. POSIX线程库2. 创建线程 pthread_create() 函数&#xff08;1&#xff09;头文件&#xff08;2&#xff09;函数原型&#xff08;3&#xff09;参数解释&#x…

微服务链路追踪组件SkyWalking实战

概述 微服务调用存在的问题 串联调用链路&#xff0c;快速定位问题&#xff1b;理清服务之间的依赖关系&#xff1b;微服务接口性能分析&#xff1b;业务流程调用处理顺序&#xff1b; 全链路追踪&#xff1a;对请求源头到底层服务的调用链路中间的所有环节进行监控。 链路…

重新认识Word——样式

重新认识Word Word样式给所有一级标题加上一级标题样式修改标题一样式&#xff0c;符合要求 正文样式标题前的小黑点导航窗格样式的相互复制Word一键转PPT 话说回来&#xff0c;一个程序员平时可能还看不起office全家桶的软件&#xff0c;但是&#xff0c;在实际的生活运用中&a…

人工智能与供应链行业融合:预测算法的通用化与实战化

文章目录 前言供应链预测算法的基本流程统计学习模型与机器学习在供应链预测中的角色深度学习模型在智能供应链中的应用算法融合与应用场景实现后记 前言 随着数字化时代的到来&#xff0c;人工智能已经逐渐成为企业信息化建设的重要手段。特别是在供应链行业&#xff0c;人工…

01-使用Git操作本地库,如初始化本地库,提交工作区文件到暂存区和本地库,查看版本信息,版本切换命令等

Git的使用 概述 Git是一个分布式版本控制工具, 通常用来管理项目中的源代码文件(Java类、xml文件、html页面等)进行管理,在软件开发过程中被广泛使用 Git可以记录文件修改的历史记录并形成备份从而实现代码回溯, 版本切换, 多人协作, 远程备份的功能Git具有廉价的本地库,方便…

微信小程序组件与插件有啥区别?怎么用?

目录 一、微信小程序介绍 二、微信小程序组件 三、微信小程序插件 四、微信小程序组件与插件有啥区别 一、微信小程序介绍 微信小程序是一种基于微信平台的应用程序&#xff0c;它可以在微信客户端内直接运行&#xff0c;无需下载和安装。微信小程序具有轻量、便捷、跨平台…

Linux 进程(三)

Linux进程状态的查看&#xff1a; 这是Linux内核源代码对于进程状态的定义&#xff1a; R运行状态&#xff08;running&#xff09;: 并不意味着进程一定在运行中&#xff0c;它表明进程要么是在运行中要么在运行队列里。 S睡眠状态&#xff08;sleeping): 意味着进程在…

乱序学机器学习——主成分分析法PCA

文章目录 概览PCA核心思想和原理PCA求解算法PCA算法代码实现降维任务代码实现PCA在数据降噪中的应用PCA在人脸识别中的应用主成分分析优缺点和适用条件优点缺点适用条件 概览 PCA核心思想和原理 PCA求解算法 特征向量表示分布的方向&#xff0c;特征值表示沿着个方向分布的程度…