青蛙跳杯子【蓝桥杯】/bfs

青蛙跳杯子

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

bfs

思路:刚开始用的是dfs,但是不太行,DFS 可能会导致搜索深度过深,增加了时间复杂度,BFS 适合求解最短路径问题,BFS 在搜索过程中,首先访问距离初始节点最近的节点,因此可以保证找到的路径是最短的,所以应该选择bfs。
本题可以以*为切入点,来进行跳跃

#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
string s1,s2;
//需要用这个来存储一个串如果已经被访问过就不用再跳了,不然会重复很多
map<string,bool> m;
ll bfs(int n)
{
    queue<pair<string,ll>> q;
    q.push({s1,0});
    while(!q.empty())
    {
        string s=q.front().first;
        //代表步数
        ll num=q.front().second;
        q.pop();
        if(s==s2) return num;
        if(m[s]) continue;
        m[s]=1;
        int idx=s.find('*');
        string temp;
        //交换左边第一个
        if(idx>0)
        {
            temp=s;
            swap(temp[idx],temp[idx-1]);
            q.push({temp,num+1});
        }
        //交换左边第二个
        if(idx>1)
        {
            temp=s;
            swap(temp[idx],temp[idx-2]);
            q.push({temp,num+1});
        }
        //交换左边第三个
        if(idx>2)
        {
            temp=s;
            swap(temp[idx],temp[idx-3]);
            q.push({temp,num+1});
        }
        //交换右边第一个
        if(idx<n-1)
        {
            temp=s;
            swap(temp[idx],temp[idx+1]);
            q.push({temp,num+1});
        }
        //交换右边第二个
        if(idx<n-2)
        {
            temp=s;
            swap(temp[idx],temp[idx+2]);
            q.push({temp,num+1});
        }
        //交换右边第三个
        if(idx<n-3)
        {
            temp=s;
            swap(temp[idx],temp[idx+3]);
            q.push({temp,num+1});
        }
    }
    return -1;
}
int main()
{
    cin>>s1>>s2;
    int n=s1.size();
    cout<<bfs(n)<<endl;
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

欧拉函数确定1-n有多少个数和 n 互质详解 附C语言代码 蓝桥杯互质数的个数

唯一分解定理 任意一个大于 1 的正整数都能被唯一地分解为质因数的乘积。 例如 8 2*2*2&#xff0c; 171 3*3*19&#xff0c; 30 2*3*5&#xff0c; 19 19。注意1既不是质数也不是合数。 为什么判断一个数是否是质数只要判断2-√n中有没有因数 24可以分解成 4*6&#x…

时序预测 | Python实现BiGRU-RELM时间序列预测

时序预测 | Python实现BiGRU-RELM时间序列预测 目录 时序预测 | Python实现BiGRU-RELM时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 BiGRU-RELM时间序列预测分析 将BiGRU和RELM两种模型进行了融合&#xff0c;BiGRU进行预测&#xff0c;RELM对BiGRU模型的预…

算法刷题Day24 | 216.组合总和III、17.电话号码的字母组合

目录 0 引言1 组合总和 III1.1 我的解题 2 电话号码的字母组合2.1 我的解题2.2 优秀的题解 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;算法专栏&#x1f4a5; 标题&#xff1a;算法刷题Day24 | 216.组合总和III、17.电话号码的字母组合❣️ 寄…

Linux基础篇:Linux第三方软件仓库——可以让Linux变得有趣的软件仓库

Linux第三方软件仓库——可以让Linux变得有趣的软件仓库 一、epel源介绍 EPEL&#xff08;Extra Packages for Enterprise Linux&#xff09;源是一个由Fedora项目组维护的第三方软件仓库&#xff0c;为企业级Linux发行版&#xff08;如Red Hat Enterprise Linux&#xff08;…

opencv+python(通道的分离与合并)笔记

分割图像通道&#xff1a; 通过函数mvsplit(img)&#xff1b;mv返回的通道&#xff1b; RGB有3个通道&#xff1b;灰度图只有一个通道&#xff1b; b,g,r cv2.split(img)cv2.imshow("b",b)#通道bcv2.imshow("g",g)#通道gcv2.imshow("r",r)#通道…

Flutter 应用数据持久化指南

1. 介绍 1.1 什么是数据持久化&#xff1f; 数据持久化是指将应用程序中的数据保存在持久存储介质&#xff08;如硬盘、数据库等&#xff09;中的过程。在计算机科学领域&#xff0c;持久化数据是指数据在程序退出或系统关机后仍然存在的能力。这种持久性使得数据可以在不同的…

为什么说“微隔离技术“ 那么重要,德迅零域给您答案

随着网络安全威胁不断增加&#xff0c;传统安全措施难以承受这种压力&#xff0c;人们需要更强大的防护工具来确保个人和组织的数据不会被攻击者窃取。 “微隔离”技术是一种在设备内部进行隔离的安全机制。它基于各种硬件或软件实现不同隔离策略&#xff0c;将不同的数据或应用…

C++——STL容器——string

目录 1.构造函数 模拟实现 2.析构函数 模拟实现 3.string遍历 3.1 c_str、size、lenth、capacity等 模拟实现 3.2 字符串元素访问 3.2.1 []操作符重载、at 模拟实现 3.2.2 front、back等 3.3 迭代器 模拟实现 4.赋值操作 4.1 赋值重载函数 模拟实现 4.2 assig…

C#手术麻醉信息系统源码,技术框架:Vue,Ant-Design+百小僧开源框架

C#手术麻醉信息系统源码&#xff0c;技术框架&#xff1a;Vue&#xff0c;Ant-Design百小僧开源框架 手术麻醉系统主要用于在手术过程中监测和控制患者的状态&#xff0c;确保手术的顺利进行并保障患者的生命安全。该系统通过一系列先进的医疗设备和技术&#xff0c;为手术患者…

【tensorflow框架神经网络实现鸢尾花分类—优化器】

文章目录 1、前言2、神经网络参数优化器2.1、SGD2.2、SGDM2.3、Adagrad2.4、RMSProp2.5、Adam 3、实验对比不同优化器4、结果对比 1、前言 此前&#xff0c;在【tensorflow框架神经网络实现鸢尾花分类】一文中使用梯度下降算法SGD&#xff0c;对权重 w w w和偏置 b b b进行更新…

多态.Java

&#xff08;1&#xff09;什么是多态&#xff1f; 同类型的对象&#xff0c;表现出不同的形态。前者指父类&#xff0c;后者指不同的子类 说简单点&#xff0c;就是父类的同一种方法&#xff0c;可以在不同子类中表现出不同的状态&#xff0c;或者说在不同子类中可以实现不同…

[技术闲聊]我对电路设计的理解(七)-Cadence原理图绘制

一、原理图软件推荐 之前的章节有讲过AD、PADS、Cadence&#xff0c;以及三者的应用标准&#xff0c;今天再讲讲这一点。 如果是学生&#xff0c;可以学习AD软件&#xff0c;因为学校在学习&#xff0c;上手容易&#xff0c;而且即使工作后&#xff0c;如果是电机控制等4层板或…

websokcet服务端实现

一/websokcet服务端实现 步骤一&#xff1a; springboot底层帮我们自动配置了websokcet&#xff0c;引入maven依赖 1 2 3 4 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-websocket</arti…

力扣刷题 二叉树遍历的统一迭代法

题干 给定一个二叉树的根节点 root &#xff0c;返回 它的 前中后序 遍历 。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,3,2]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[]示例 3&#xff1a; 输入&#xff1a;root […

Python 之 Fastapi 框架学习

依赖安装 Fastapi 有版本要求&#xff0c;需要的 Python 版本至少是 Python 3.8&#xff08;不要犟&#xff0c;按照版本要求来&#xff0c;我最先也是在我 Python3.6 上装的&#xff0c;果不其然跑不起来&#xff09;&#xff0c;幸好我 Win7 老古董能支持的 Python 最高版本…

FastWiki发布`0.2.4`支持js 函数

Release v0.2.4 AIDotNet/fast-wiki (github.com) 支持JS动态functioncall调用支持动态function管理支持JS在线编辑提供智能代码提示支持JS在线编辑提供部分绑定的c#类&#xff08;默认提供Console&#xff0c;HttpClient&#xff09;支持Application绑定多个Function Call优…

跨站请求伪造漏洞(CSRF)

什么是CSRF CSRF&#xff08;Cross-Site Request Forgery&#xff09;&#xff0c;也被称为 one-click attack 或者 session riding&#xff0c;即跨站请求伪造攻击。 漏洞原理 跨站请求伪造漏洞的原理主要是利用了网站对用户请求的验证不严谨。攻击者会在恶意网站中构造一个…

linux 文件提权|属性修改

文章目录 suid&#xff08;set uid&#xff09;添加文件属性查看文件属性i &#xff08;immutable&#xff09; umask suid&#xff08;set uid&#xff09; 让文件在执行的时候具有属主&#xff08;对应文件 user &#xff09;的权限 chmod 7744 temp.txt 第一位的7表示权限位…

探寻大数据思想的主要贡献者与核心内容

引言&#xff1a; 在当今数字化时代&#xff0c;大数据已成为企业和科学研究的关键要素。其背后的思想和概念不仅引领了数据处理和分析的革新&#xff0c;也推动了人类对于信息时代的理解与认知。 大数据思想的起源&#xff1a; 在信息爆炸的时代背景下&#xff0c;大数据思…

海外仓的出入库流程有什么痛点?位像素海外仓系统怎么提高出入库效率?

随着跨境电商的蓬勃发展&#xff0c;海外仓是其中不可或缺的一个关键环节。而货物的出库与入库则是海外仓管理中的一个核心业务流程&#xff0c;它的运作效率直接影响到整个跨境物流的效率和客户体验。今天&#xff0c;让我们具体来看一看关于海外仓出入库的流程&#xff0c;其…