备战蓝桥杯---搜索(应用入门)
话不多说,直接看题:


显然,我们可以用BFS,其中,对于判重操作,我们可以把这矩阵化成字符串的形式再用map去存,用a数组去重现字符串(相当于map映射的反向操作)。移动空格先找到x的位置再推算出在矩阵里的位置进行移动即可。
至于如何回溯,我们创造last数组来看它上一个是谁,用form数组记录变化的操作。
然后dfs回溯输出即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
#define N 363000
int last[N],cnt;
int form[N];
char dd;
map<string,int> mp;
string a[N],s1,s2="12345678x";
queue<int> q;
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
char ck[4]={'r','l','u','d'};
int bfs(string s1,string s2){mp[s1]=1;cnt=1;last[cnt]=0;a[cnt]=s1;q.push(cnt);while(!q.empty()){int tmp=q.front();q.pop();int tt=a[tmp].find('x');int x=tt/3,y=tt%3;for(int i=0;i<4;i++){string nxt=a[tmp];int x1=x+dir[i][0];int y1=y+dir[i][1];if(x1<0||x1>=3||y1<0||y1>=3) continue;swap(nxt[tt],nxt[x1*3+y1]);if(mp.find(nxt)!=mp.end()) continue;mp[nxt]=++cnt;last[cnt]=tmp;form[cnt]=i;a[cnt]=nxt;q.push(cnt);if(nxt==s2) return 1;}}return 0;
}
void dfs(int cnt){if(cnt==1) return;dfs(last[cnt]);cout<<ck[form[cnt]];
}
int main(){for(int i=1;i<=9;i++){cin>>dd;s1+=dd;}if(bfs(s1,s2)==0) cout<<"unsolvable";else dfs(mp[s2]);
}
注意:方向数组中(1,0)是down(因为这wa了好久)
下面来一道刚刚比赛过的题:

这名字显然是个坑,看到数据范围就知道要暴力了3^10是可以接受的,于是我们用dfs写
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[20],min1=20;
struct node{int u,v;
}q[20];
void deal(){int cnt=1;for(int i=2;i<=n;i++){if(a[i]>a[1]) cnt++;}min1=min(min1,cnt);
}
void dfs(int x){if(x>m){deal();return ;}for(int i=1;i<=3;i++){if(i==1){a[q[x].u]+=3;dfs(x+1);a[q[x].u]-=3;}else if(i==2){a[q[x].v]+=3;dfs(x+1);a[q[x].v]-=3;}else{a[q[x].u]+=1;a[q[x].v]+=1;dfs(x+1);a[q[x].u]-=1;a[q[x].v]-=1;}}return ;
}
int main(){cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>q[i].u>>q[i].v;dfs(1);cout<<min1<<endl;min1=20;}
}
相关文章:
备战蓝桥杯---搜索(应用入门)
话不多说,直接看题: 显然,我们可以用BFS,其中,对于判重操作,我们可以把这矩阵化成字符串的形式再用map去存,用a数组去重现字符串(相当于map映射的反向操作)。移动空格先找…...
自学PyQt6杂记索引
文章目录 📖 介绍 📖🏡 安装 🏡📒 使用 📒📝 QtCore📝 QtGui📝 QtWidgets📝 QToolTip📝 信号和槽📝 QtDBus📝 QtNetwork📝 QtHelp📝 QtXml📝 QtSvg...
【Docker】Docker Registry(镜像仓库)
文章目录 一、什么是 Docker Registry二、镜像仓库分类三、镜像仓库工作机制四、常用的镜像仓库五、常用命令镜像仓库命令镜像命令(部分)容器命令(部分) 六、docker镜像仓库实战综合实战一:搭建一个 nginx 服务综合实战二:Docker hub上创建自己私有仓库综…...
TensorFlow2实战-系列教程14:Resnet实战2
🧡💛💚TensorFlow2实战-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Jupyter Notebook中进行 本篇文章配套的代码资源已经上传 Resnet实战1 Resnet实战2 Resnet实战3 4、训练脚本train.py解读------创建模型 def …...
编程笔记 html5cssjs 069 JavaScript Undefined数据类型
编程笔记 html5&css&js 069 JavaScript Undefined数据类型 一、undefined数据类型二、类型运算小结 在JavaScript中,undefined 是一种基本数据类型,它表示一个变量已经声明但未定义(即没有赋值)或者一个对象属性不存在。 …...
《区块链简易速速上手小册》第6章:区块链在金融服务领域的应用(2024 最新版)
文章目录 6.1 金融服务中的区块链6.1.1 金融服务中区块链的基础6.1.2 主要案例:跨境支付6.1.3 拓展案例 1:去中心化金融(DeFi)6.1.4 拓展案例 2:代币化资产 6.2 区块链在支付系统中的作用6.2.1 支付系统中区块链的基础…...
【消息队列】kafka整理
kafka整理 整理kafka基本知识供回顾。...
python--杂识--16--代理密码中包含特殊字符
1 安装nginx 2 centos环境安装 yum install httpd-tools3 nginx.conf /etc/nginx/conf/nginx.conf #user nobody; worker_processes 1;#error_log logs/error.log; #error_log logs/error.log notice; #error_log logs/error.log info;#pid logs/nginx.pid;e…...
【Git】05 分离头指针
文章目录 一、分离头指针二、创建分支三、比较commit内容四、总结 一、分离头指针 正常情况下,在通过git checkout命令切换分支时,在命令后面跟着的是分支名(例如master、temp等)或分支名对应commit的哈希值。 非正常情况下&…...
【Tomcat与网络9】提高Tomcat启动速度的八大措施
本文我们来看一下如何对Tomcat进行调优,我们对于Tomcat的调优主要集中在三个方面:提高启动速度、提高系统稳定性和提高并发能力,后两者很多时候是相辅相成的,我们放在一起看。 Tomcat现在一般都嵌入在SpringBoot里,因…...
蓝桥杯嵌入式第七届真题(完成) STM32G431
蓝桥杯嵌入式第七届真题(完成) STM32G431 题目 相关文件 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program body**********************…...
如何降低视频RTSP解码延迟
降低RTSP(Real-Time Streaming Protocol)视频流的解码延迟涉及到网络传输和解码处理的优化。以下是一些常见的方法: 选择低延迟的解码器:使用专为低延迟优化的解码器,例如一些定制的H.264或H.265解码器。 优化解码器设…...
【Golang】自定义logrus日志保存为日志文件
背景 为了方便查看日志,项目中需要把日志保存到对应的日志文件中,所以需要当前的配置,以使得日志能够保存到对应的日志文件中。 代码 import ("github.com/orandin/lumberjackrus""github.com/sirupsen/logrus" )func …...
【大厂AI课学习笔记】1.4 算法的进步(4)关于李飞飞团队的ImageNet
第一个图像数据库是ImageNet,由斯坦福大学的计算机科学家李飞飞推出。ImageNet是一个大型的可视化数据库,旨在推动计算机视觉领域的研究。这个数据库包含了数以百万计的手工标记的图像,涵盖了数千个不同的类别。 基于ImageNet数据库…...
【Linux笔记】缓冲区的概念到标准库的模拟实现
一、缓冲区 “缓冲区”这个概念相信大家或多或少都听说过,大家其实在C语言阶段就已经接触到“缓冲区”这个东西,但是相信大家在C语言阶段并没有真正弄懂缓冲区到底是个什么东西,也相信大家在C语言阶段也因为缓冲区的问题写出过各种bug。 其…...
【前端收藏】前端小作文-前端八股文知识总结(超万字超详细)持续更新
有了这个八股文不仅对你基础知识的巩固,不管你是几年老前端程序员,还是要去面试的,文章覆盖了前端常用及不常用的方方面面,都是前端日后能用上的,对你的前端知识有总结意义,看完后,懂的不懂的都…...
GNSS模块的惯导技术:引领定位科技的前沿
全球导航卫星系统(GNSS)模块的惯导技术是一项颇具前瞻性的科技,它结合了全球定位系统和惯性导航技术,为各个领域的定位需求提供了更为精准和可靠的解决方案。本文将深入探讨GNSS模块的惯导技术,以及它如何在多个领域中…...
Flutter 和 Android原生(Activity、Fragment)相互跳转、传参
前言 本文主要讲解 Flutter 和 Android原生之间,页面相互跳转、传参, 但其中用到了两端相互通信的知识,非常建议先看完这篇 讲解通信的文章: Flutter 与 Android原生 相互通信:BasicMessageChannel、MethodChannel、…...
Kubernetes基础(十一)-CNI网络插件用法和对比
1 CNI概述 1.1 什么是CNI? Kubernetes 本身并没有实现自己的容器网络,而是借助 CNI 标准,通过插件化的方式来集成各种网络插件,实现集群内部网络相互通信。 CNI(Container Network Interface,容器网络的…...
yo!这里是单例模式相关介绍
目录 前言 特殊类设计 只能在堆上创建对象的类 1.方法一(构造函数下手) 2.方法二(析构函数下手) 只能在栈上创建对象的类 单例模式 饿汉模式实现 懒汉模式实现 后记 前言 在面向找工作学习c的过程中,除了基本…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
