当前位置: 首页 > news >正文

八数码(bfs)

思路:

(1)用string来存储状态,用d<string,int>来记录状态变换次数;

(2)在bfs过程中,先初始化(q,d);每次拿出队头状态,得到x的相对位置,再得到x的矩阵位置,向四个方向尝试走,如果可行,就先做变换,如果该状态没被使用过即没有走回头路,就更新放入队列,另一方面维护d距离;然后恢复现场保证其余三个方向继续使用;如果所有状态都探讨完毕也没有可行解,就输出-1;

代码:

#include<bits/stdc++.h>using namespace std;int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};void bfs(string start)
{queue<string> q;unordered_map<string,int> d;string end = "12345678x";q.push(start);d[start] = 0;while(!q.empty()){string tmp = q.front();int k = tmp.find('x');q.pop();int x = k/3,y = k%3;int dis = d[tmp];if(tmp == end){cout << d[end] << endl;return;}for(int i = 0;i < 4;i ++){int tx = x + dx[i],ty = y + dy[i];if(tx >=0 && ty >= 0 && tx < 3 && ty < 3){swap(tmp[k],tmp[tx*3 + ty]);if(d.count(tmp) == 0){d[tmp] = dis + 1;q.push(tmp);}swap(tmp[k],tmp[tx*3 + ty]);}}}cout << -1<<endl;return;
}int main()
{string start;for(int i = 0;i < 9;i ++){char c;cin >> c;start = start + c;}bfs(start);return 0;
}

相关文章:

八数码(bfs)

思路&#xff1a; &#xff08;1&#xff09;用string来存储状态&#xff0c;用d<string,int>来记录状态变换次数&#xff1b; &#xff08;2&#xff09;在bfs过程中&#xff0c;先初始化&#xff08;q,d)&#xff1b;每次拿出队头状态&#xff0c;得到x的相对位置&am…...

CCLINK IE FIELD BASIC转MODBUS-TCP网关cclink与以太网的区别

协议的不同&#xff0c;数据读取困难&#xff0c;这是很多生产管理系统的难题。但是现在&#xff0c;捷米JM-CCLKIE-TCP通讯网关&#xff0c;让这个问题变得非常简单。这款通讯网关可以将各种MODBUS-TCP设备接入到CCLINK IE FIELD BASIC网络中&#xff0c;连接到MODBUS-TCP总线…...

【Rust】Rust学习 第十一章编写自动化测试

Rust 是一个相当注重正确性的编程语言&#xff0c;不过正确性是一个难以证明的复杂主题。Rust 的类型系统在此问题上下了很大的功夫&#xff0c;不过它不可能捕获所有种类的错误。为此&#xff0c;Rust 也在语言本身包含了编写软件测试的支持。 编写一个叫做 add_two 的将传递…...

关于使用pycharm遇到只能使用unittest方式运行,无法直接选择Run

相信大家可能都遇到过这个问题&#xff0c;使用pycharm直接运行脚本的时候&#xff0c;只能选择unittest的方式&#xff0c;能愁死个人 经过几次各种尝试无果之后&#xff0c;博主就放弃死磕了&#xff0c;原谅博主是个菜鸟 后来遇到这样的问题&#xff0c;往往也就直接使用cm…...

Docker+rancher部署SkyWalking8.5并应用在springboot服务中

1.Skywalking介绍 Skywalking是一个国产的开源框架&#xff0c;2015年有吴晟个人开源&#xff0c;2017年加入Apache孵化器&#xff0c;国人开源的产品&#xff0c;主要开发人员来自于华为&#xff0c;2019年4月17日Apache董事会批准SkyWalking成为顶级项目&#xff0c;支持Jav…...

代码随想录第45天 | 322. 零钱兑换、279. 完全平方数

322. 零钱兑换 动规五部曲分析如下&#xff1a; 确定dp数组以及下标的含义 dp[j]&#xff1a;凑足总额为j所需钱币的最少个数为dp[j] 确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]&#xff0c;那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是…...

怎么加入Microsoft Cloud Partner Program?

目录 前言 加入Microsoft Cloud Partner Program 1、注册成为微软合作伙伴 2、完成合作伙伴资格要求...

LNMP简易搭建

目录 前言 一、拓扑图 二、NGINX配置 三、配置MySQL 四、配置php环境 五、部署应用 总结 前言 LNMP平台指的是将Linux、Nginx、MySQL和PHP&#xff08;或者其他的编程语言&#xff0c;如Python、Perl等&#xff09;集成在一起的一种Web服务器环境。它是一种常用的开发和部署网…...

CClink IE转Modbus TCP网关连接三菱FX5U PLC

捷米JM-CCLKIE-TCP 是自主研发的一款 CCLINK IE FIELD BASIC 从站功能的通讯网关。该产品主要功能是将各种 MODBUS-TCP 设备接入到 CCLINK IE FIELD BASIC 网络中。 捷米JM-CCLKIE-TCP网关连接到 CCLINK IE FIELD BASIC 总线中做为从站使用&#xff0c;连接到 MODBUS-TCP 总线…...

PyTorch 微调终极指南:第 1 部分 — 预训练模型及其配置

一、说明 如今&#xff0c;在训练深度学习模型时&#xff0c;通过在自己的数据上微调预训练模型来迁移学习已成为首选方法。通过微调这些模型&#xff0c;我们可以利用他们的专业知识并使其适应我们的特定任务&#xff0c;从而节省宝贵的时间和计算资源。本文分为四个部分&…...

GO学习之 微框架(Gin)

GO系列 1、GO学习之Hello World 2、GO学习之入门语法 3、GO学习之切片操作 4、GO学习之 Map 操作 5、GO学习之 结构体 操作 6、GO学习之 通道(Channel) 7、GO学习之 多线程(goroutine) 8、GO学习之 函数(Function) 9、GO学习之 接口(Interface) 10、GO学习之 网络通信(Net/Htt…...

C语言 字符指针

1、介绍 概念&#xff1a; 字符指针&#xff0c;就是字符类型的指针&#xff0c;同整型指针&#xff0c;指针指向的元素表示整型一样&#xff0c;字符指针指向的元素表示的是字符。 假设&#xff1a; char ch a;char * pc &ch; pc 就是字符指针变量&#xff0c;字符指…...

Springboot所有的依赖

<properties><maven.compiler.source>8</maven.compiler.source><maven.compiler.target>8</maven.compiler.target><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><!-- 声明springboot的版本号 -->…...

Flutter BottomSheet 三段式拖拽

BottomSheetBehavior 追踪 BottomSheet系统默认实现效果准备要实现的功能点&#xff1a;定义三段式状态&#xff1a;BottomSheetBehavoir阀值定义1. 未达到滚动阀值&#xff0c;恢复状态2. 达到滚动阀值&#xff0c;更新状态 前面倒是有讲过Android原生的BottomSheetBehavior&a…...

php后端实现调用高德地图进行POI搜索

对于当前位置或者选定省市位置进行查询 接口实现 /*** 查询地址* ApiTitle (查询地址)* ApiSummary (查询地址)* ApiMethod (POST)* ApiRoute (/api/demo/address)* ApiParams (name"dart", type"integer", requiredtrue, description"省…...

uniapp 实现滑动视图切换 顶部滚动导航栏

无论小程序的时候一般有这个功能,在页面处于首页时候,滑动视图,切换视图顶部滚动导航也跟着切换 1.想要实现这个功能就需要实现顶部导航栏,首先实现顶部滚导航栏 点击高亮颜色显示 模板代码 <scroll-view scroll-x"true" class"scroll-content" > …...

ArcGIS API for JavaScript 调用自定义地图模板总结

ArcGIS API for JavaScript 调用自定义地图模板总结 3.9版本4.24版本 3.9版本 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>Hello World</title><link rel"stylesheet" href&qu…...

QGraphicsView实现简易地图5『经纬网格』

前文链接&#xff1a;QGraphicsView实现简易地图4『局部加载-地图漫游』 由于GCJ02 Web 墨卡托投影 纬度并不随像素等分&#xff0c;且两极跨度较大&#xff0c;因此本次演示采用的经纬网等分逻辑为等分像素。同等像素跨度之间&#xff0c;两级纬度变化较小&#xff0c;越靠近赤…...

RestTemplate 请求转发异常 ERR_CONTENT_DECODING_FAILED 200 (OK)

#1 问题描述 在基于Spring Boot的项目中实现了请求转发&#xff08;使用 RestTemplate 的 exchange 方法&#xff09;的功能&#xff0c;忽然在前端报net::ERR_CONTENT_DECODING_FAILED 200 (OK)的错误&#xff0c;后端及上游系统日志均显示请求已完成。 #2 原因探寻 上述错…...

用python实现一个异或计算器

有这样一条需求&#xff1a;计算某个文件中的数组每一行元素的最后一个参数&#xff0c;异或输出。 因为元素比较多&#xff0c;十几行&#xff0c;通过人工去计算异或值非常困难。 而在线异或的计算器&#xff0c;也需要人为输入这些数值&#xff0c;每次计算一个最终结果需…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...

SOC-ESP32S3部分:30-I2S音频-麦克风扬声器驱动

飞书文档https://x509p6c8to.feishu.cn/wiki/SKZzwIRH3i7lsckUOlzcuJsdnVf I2S简介 I2S&#xff08;Inter-Integrated Circuit Sound&#xff09;是一种用于传输数字音频数据的通信协议&#xff0c;广泛应用于音频设备中。 ESP32-S3 包含 2 个 I2S 外设&#xff0c;通过配置…...

SQLSERVER-DB操作记录

在SQL Server中&#xff0c;将查询结果放入一张新表可以通过几种方法实现。 方法1&#xff1a;使用SELECT INTO语句 SELECT INTO 语句可以直接将查询结果作为一个新表创建出来。这个新表的结构&#xff08;包括列名和数据类型&#xff09;将与查询结果匹配。 SELECT * INTO 新…...

Spring Boot 与 Kafka 的深度集成实践(二)

3. 生产者实现 3.1 生产者配置 在 Spring Boot 项目中&#xff0c;配置 Kafka 生产者主要是配置生产者工厂&#xff08;ProducerFactory&#xff09;和 KafkaTemplate 。生产者工厂负责创建 Kafka 生产者实例&#xff0c;而 KafkaTemplate 则是用于发送消息的核心组件&#x…...