Python:青蛙跳杯子(BFS)
题目描述
X 星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。
X 星球的居民喜欢把它们放在一排茶杯里,这样可以观察它们跳来跳去。
如下图,有一排杯子,左边的一个是空着的,右边的杯子,每个里边有一只青蛙。
∗WWWBBB
其中,W 字母表示白色青蛙,B 表示黑色青蛙,∗ 表示空杯子。
X 星的青蛙很有些癖好,它们只做 3 个动作之一:
-
跳到相邻的空杯子里。
-
隔着 1 只其它的青蛙(随便什么颜色)跳到空杯子里。
-
隔着 2 只其它的青蛙(随便什么颜色)跳到空杯子里。
对于上图的局面,只要 1 步,就可跳成下图局面:
WWW∗BBB
本题的任务就是已知初始局面,询问至少需要几步,才能跳成另一个目标局面。
输入描述
输入为 2 行,2 个串,表示初始局面和目标局面。我们约定,输入的串的长度不超过 15。
输出描述
输出要求为一个整数,表示至少需要多少步的青蛙跳。
输入输出样例
示例
输入
*WWBB
WWBB*
输出
2
思路:
参考代码:
import sys
chushi = input()
mubiao = input()
lis = [1,-1,2,-2,3,-3]
experience = {chushi} #标记状态
queue= [[chushi,0]] #状态和层数
while queue: #若不为空old = queue.pop(0) #弹出第一个元素for i in lis:state = list(old[0]) #字符串转化为列表step = old[1]kgwz = state.index('*') #查找空格位置xkgwz = kgwz + i #新空格位置if 0<=xkgwz<len(chushi): #判断新空格位置是否出界state[kgwz] = state[xkgwz]state[xkgwz] = '*'new_state = "".join(state)step += 1if new_state == mubiao:print(step)sys.exit(0) #程序终止if new_state not in experience: #若新状态没有出现过以前的状态中experience.add(new_state)queue.append([new_state,step])
相关文章:
Python:青蛙跳杯子(BFS)
题目描述 X 星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。 X 星球的居民喜欢把它们放在一排茶杯里,这样可以观察它们跳来跳去。 如下图,有一排杯子,左边的一个是空着的,右边的杯子,每个…...
6.10 谱分解
文章目录计算方法代码实现计算方法 单纯矩阵normal matrix指的是符号ATAAATA^TAAA^TATAAAT的矩阵,他们的特征值互异。此外,单纯矩阵还有个特点,他们的特征空间彼此正交。 对于单纯矩阵,存在以下的谱定理Spectral theorem&…...
MySQL入门篇-MySQL 行转列小结
备注:测试数据库版本为MySQL 8.0 需求:求emp表各个岗位的工资之和,如无,用0代替 如需要scott用户下建表及录入数据语句,可参考:scott建表及录入数据sql脚本 CASE语法 SELECT deptno,ifnull(sum(case when job MANAGER then sal else 0 …...
项目管理常见的十大难题及其症状
01缺少维护文档时常,项目工作紧张时,第一个去掉的就是文档工作。有时即使项目有时间,也不会创建文档;或是创建了文档,却很少在项目进行过程中维护它。症状产品与需求文档不符;技术文档过时,无法保证技术的延…...
技术方案模板
0.基本原则 1.可量化,很大、很多、很高 到底是多少?基本没影响,到底有没有影响什么情况下有影响? 2.可实施,结合实际情况最终可落地 3.可指导,非方案制定人能理解,能在尽量少的人工沟通的情况下实现方案 4.可复用,设计的方案,再次出现类似需求时可以做到少开发或不…...

MySQL中对于单表和多表的操作
一、单表查询素材: 表名:worker-- 表中字段均为中文,比如 部门号 工资 职工号 参加工作 等显示所有职工的基本信息。mysql8.0 [chap03]>select * from worker;查询所有职工所属部门的部门号,不显示重复的部门号。mysql8.0 [cha…...
MFI认证
一、什么是MFI认证? 苹果MFI认证,是苹果公司(Apple Inc.)对其授权配件厂商生产的外置配件的一种使用许可,MFi认证是apple公司Made for iPhone/iPad/iPod的英文缩写。是指分别为连接iPhone/iPad/iPod而特别设计的电子配件。 [图片] 二、iOS外设连接的几种方式 [图片] 这…...
Vue中mixins的使用
文章目录mixins介绍mixins特点mixins介绍 Mixins:在引入组件之后与组件中的对象和方法进行合并,相当于扩展了父组件的对象与方法,可以理解为形成了一个新的组件。混入 (mixins):是一种分发 Vue 组件中可复用功能的非常灵活的方式…...

【PyQt】PyQt学习(一)框架介绍+环境搭建
简介 写在最前面的话 在决定学习、使用一个框架之前需要考量如下几点: 框架运行效果;框架应用范围;框架学习成本和迁移成本;实现自己所需功能的开发效率; 只有综合考量如上四个方面,才能更好地选择适合…...

浅谈前端设计模式:策略模式和状态模式的异同点
一、策略模式 策略模式是定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。 而且策略模式是重构小能力,特别适合拆分“胖逻辑”。 这个定义乍一看会有点懵,不过通过下面的例子就能慢慢理解它的意思。 先来看一个真实场景 某次活动要做…...

线性杂双功能PEG试剂OPSS-PEG-Acid,OPSS-PEG-COOH,巯基吡啶聚乙二醇羧基
英文名称:OPSS-PEG-COOH,OPSS-PEG-Acid 中文名称:巯基吡啶-聚乙二醇-羧基 OPSS-PEG-COOH是一种具有OPSS和羧基的线性杂双功能PEG试剂。它是一种有用的带有PEG间隔基的交联剂。OPSS代表正吡啶基二硫化物或邻吡啶基二硫代,与硫醇、…...

开发微服务电商项目演示(四)
一,网关服务限流熔断降级第1步:启动sentinel-dashboard控制台和Nacos注册中心服务第2步:在网关服务中引入sentinel依赖<!-- sentinel --> <dependency><groupId>com.alibaba.cloud</groupId><artifactId>sprin…...

【C语言学习笔记】:静态库
一、什么是库 库是写好的现有的,成熟的,可以复用的代码。现实中每个程序都要依赖很多基础的底层库,不可能每个人的代码都从零开始,因此库的存在意义非同寻常。 本质上来说库是一种可执行代码的二进制形式,可以被操作…...

社科院与杜兰大学中外合作办学金融管理硕士——30+的年龄在职读研有必要吗?
说起读研,年龄在什么区间最合适呢?上次有位咨询的同学反馈年龄已经快35岁了,有一份不错的工作,但又不甘心止步于此,想要通过提升学历升职加薪,但又纠结自己是否能静下心来学习、是否能顺利毕业、拿到的证书…...

2.13作业【设备树解析,按自己理解】
设备树定义 设备树(device tree是描述硬件信息的一种树形结构,设备书文件在linux内核启动后被内核解析。描述一个硬件设备信息的节点我们叫做设备节点,一个设备节点内部包含当前硬件的多个不同属性,相同节点不同属性是以链式结构存…...
《NFL星计划》:巴尔的摩乌鸦·橄榄1号位
巴尔的摩乌鸦(英语:Baltimore Ravens)是一支职业美式橄榄球球队位于马里兰州的巴尔的摩。他们现时为美国美式橄榄球联合会的北区进行比赛,其主场为M&T银行体育场。乌鸦队曾在2000年和2012年取得超级碗冠军。 巴尔的摩乌鸦 成…...

Allegro如何设置自动保存和自动保存的时间操作指导
Allegro如何设置自动保存和自动保存的时间操作指导 做PCB设计的时候,自动保存软件是一个必要的功能,Allegro同样支持设置自动保存,而且可以设置自动保存的时间。 如下图 具体操作如下 点击Setup点击User Preferences...

Kotlin实现简单音乐播放器
关于音乐播放器,我真的是接触比较多,听歌作为我第一大爱好,之前也用Java设计过音乐播放器,感兴趣的同学可以阅读:Android Studio如何实现音乐播放器(简单易上手)和 Android Studio实现音乐播放器…...

ShardingSphere-Proxy 数据库协议交互解读
数据库协议对于大部分开发者来说算是比较冷门的知识,一般的用户、开发者都是通过现成的数据库客户端、驱动使用数据库,不会直接操作数据库协议。不过,对数据库协议的特点与流程有一些基本的了解,有助于开发者在排查数据库功能、性…...

基于ubuntu20.4的wine的MDK5软件的安装
本文基于ubuntu20.4安装MDK5的keil软件,由于MDK不提供linux版本的安装软件,因此需要利用wine软件来安装MDK5软件,具体流程包括wine软件安装、MDK5安装及MDK5的lic添加等3部分内容。具体流程如下所示: (一)…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...