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

Python:青蛙跳杯子(BFS)

题目描述

X 星球的流行宠物是青蛙,一般有两种颜色:白色和黑色。

X 星球的居民喜欢把它们放在一排茶杯里,这样可以观察它们跳来跳去。

如下图,有一排杯子,左边的一个是空着的,右边的杯子,每个里边有一只青蛙。

∗WWWBBB

其中,W 字母表示白色青蛙,B 表示黑色青蛙,∗ 表示空杯子。

X 星的青蛙很有些癖好,它们只做 3 个动作之一:

  1. 跳到相邻的空杯子里。

  2. 隔着 1 只其它的青蛙(随便什么颜色)跳到空杯子里。

  3. 隔着 2 只其它的青蛙(随便什么颜色)跳到空杯子里。

对于上图的局面,只要 1 步,就可跳成下图局面:

WWW∗BBB

本题的任务就是已知初始局面,询问至少需要几步,才能跳成另一个目标局面。

输入描述

输入为 2 行,2 个串,表示初始局面和目标局面。我们约定,输入的串的长度不超过 15。

输出描述

输出要求为一个整数,表示至少需要多少步的青蛙跳。

输入输出样例

示例

输入

*WWBB
WWBB*

输出

2

 思路:

当前状态可能的变化状态:
        1、左\右移一个格到 空格位置
        2、左\右移两个格到 空格位置
        3、左\右移三个格到 空格位置
任务要求是从初始状态到目标状态最短路径(最少跳动次数)
搜索跳动一次所有的可能结果,并保存所以可能性作为下次搜索的初始状态。

参考代码:

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 星球的流行宠物是青蛙&#xff0c;一般有两种颜色&#xff1a;白色和黑色。 X 星球的居民喜欢把它们放在一排茶杯里&#xff0c;这样可以观察它们跳来跳去。 如下图&#xff0c;有一排杯子&#xff0c;左边的一个是空着的&#xff0c;右边的杯子&#xff0c;每个…...

6.10 谱分解

文章目录计算方法代码实现计算方法 单纯矩阵normal matrix指的是符号ATAAATA^TAAA^TATAAAT的矩阵&#xff0c;他们的特征值互异。此外&#xff0c;单纯矩阵还有个特点&#xff0c;他们的特征空间彼此正交。   对于单纯矩阵&#xff0c;存在以下的谱定理Spectral theorem&…...

MySQL入门篇-MySQL 行转列小结

备注:测试数据库版本为MySQL 8.0 需求:求emp表各个岗位的工资之和&#xff0c;如无&#xff0c;用0代替 如需要scott用户下建表及录入数据语句&#xff0c;可参考:scott建表及录入数据sql脚本 CASE语法 SELECT deptno,ifnull(sum(case when job MANAGER then sal else 0 …...

项目管理常见的十大难题及其症状

01缺少维护文档时常&#xff0c;项目工作紧张时&#xff0c;第一个去掉的就是文档工作。有时即使项目有时间&#xff0c;也不会创建文档&#xff1b;或是创建了文档&#xff0c;却很少在项目进行过程中维护它。症状产品与需求文档不符;技术文档过时&#xff0c;无法保证技术的延…...

技术方案模板

0.基本原则 1.可量化,很大、很多、很高 到底是多少?基本没影响,到底有没有影响什么情况下有影响? 2.可实施,结合实际情况最终可落地 3.可指导,非方案制定人能理解,能在尽量少的人工沟通的情况下实现方案 4.可复用,设计的方案,再次出现类似需求时可以做到少开发或不…...

MySQL中对于单表和多表的操作

一、单表查询素材&#xff1a; 表名&#xff1a;worker-- 表中字段均为中文&#xff0c;比如 部门号 工资 职工号 参加工作 等显示所有职工的基本信息。mysql8.0 [chap03]>select * from worker;查询所有职工所属部门的部门号&#xff0c;不显示重复的部门号。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&#xff1a;在引入组件之后与组件中的对象和方法进行合并&#xff0c;相当于扩展了父组件的对象与方法&#xff0c;可以理解为形成了一个新的组件。混入 (mixins)&#xff1a;是一种分发 Vue 组件中可复用功能的非常灵活的方式…...

【PyQt】PyQt学习(一)框架介绍+环境搭建

简介 写在最前面的话 在决定学习、使用一个框架之前需要考量如下几点&#xff1a; 框架运行效果&#xff1b;框架应用范围&#xff1b;框架学习成本和迁移成本&#xff1b;实现自己所需功能的开发效率&#xff1b; 只有综合考量如上四个方面&#xff0c;才能更好地选择适合…...

浅谈前端设计模式:策略模式和状态模式的异同点

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

线性杂双功能PEG试剂OPSS-PEG-Acid,OPSS-PEG-COOH,巯基吡啶聚乙二醇羧基

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

开发微服务电商项目演示(四)

一&#xff0c;网关服务限流熔断降级第1步&#xff1a;启动sentinel-dashboard控制台和Nacos注册中心服务第2步&#xff1a;在网关服务中引入sentinel依赖<!-- sentinel --> <dependency><groupId>com.alibaba.cloud</groupId><artifactId>sprin…...

【C语言学习笔记】:静态库

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

社科院与杜兰大学中外合作办学金融管理硕士——30+的年龄在职读研有必要吗?

说起读研&#xff0c;年龄在什么区间最合适呢&#xff1f;上次有位咨询的同学反馈年龄已经快35岁了&#xff0c;有一份不错的工作&#xff0c;但又不甘心止步于此&#xff0c;想要通过提升学历升职加薪&#xff0c;但又纠结自己是否能静下心来学习、是否能顺利毕业、拿到的证书…...

2.13作业【设备树解析,按自己理解】

设备树定义 设备树&#xff08;device tree是描述硬件信息的一种树形结构&#xff0c;设备书文件在linux内核启动后被内核解析。描述一个硬件设备信息的节点我们叫做设备节点&#xff0c;一个设备节点内部包含当前硬件的多个不同属性&#xff0c;相同节点不同属性是以链式结构存…...

《NFL星计划》:巴尔的摩乌鸦·橄榄1号位

巴尔的摩乌鸦&#xff08;英语&#xff1a;Baltimore Ravens&#xff09;是一支职业美式橄榄球球队位于马里兰州的巴尔的摩。他们现时为美国美式橄榄球联合会的北区进行比赛&#xff0c;其主场为M&T银行体育场。乌鸦队曾在2000年和2012年取得超级碗冠军。 巴尔的摩乌鸦 成…...

Allegro如何设置自动保存和自动保存的时间操作指导

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

Kotlin实现简单音乐播放器

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

ShardingSphere-Proxy 数据库协议交互解读

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

基于ubuntu20.4的wine的MDK5软件的安装

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

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...