蓝桥python—— 剪邮票【2016 第七题】
发布日期:2021-06-28 22:05:38
浏览次数:3
分类:技术文章
本文共 1301 字,大约阅读时间需要 4 分钟。
蓝桥python—— 剪邮票【2016 第七题】
题目描述 如【图 1.jpg】, 有 12 张连在一起的 12 生肖的邮票。 现在你要从中剪下 5 张来,要求必须 是连着的。 (仅仅连接一个角不算相连) 比如,【图 2.jpg】,【图 3.jpg】中,粉红色所 示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。 请填写表示方案数目的整数。 注意:你提交的应该是一个整数,不要填写任何多余的内容 或说明性文字。先给大家说下这个题目拿过来我的思路吧 首先题目的意思是有12个框框,我们要选择5个框框,再来判断是否连通,若联通,则答案加1
python的话从12个框框中选5个很简单,即调用itertools.combinations函数(记住是组合而不是排列)
但是要判断是否联通,对于两个框框肯定是相邻的,题目上标注的数字的话则是两个框框之差绝对值为1或者4!可是有个问题,就是绝对值为1的不一定相邻,比如 8 9
因此我们可以把以上的图变(想成)为下面的
说明:改数字对结果毫无影响,只是让我们更好判断是否连通 显然我们看到 只要两个框框之差绝对值为 1或者5 就一定相邻在12个框框中选择5个后,我们用bfs算法判断这个5个框框是否连通。
代码如下
import itertoolsdef isLiant(x):##相当于BFS,找出每个框框的所有相邻框框后判断 q=[] q.append(x[0]) seen=set() seen.add(x[0]) while len(q)>0: n=q.pop(0) if n-1 in x and n-1 not in seen: q.append(n-1) seen.add(n-1) if n+1 in x and n+1 not in seen: q.append(n+1) seen.add(n+1) if n-5 in x and n-5 not in seen: q.append(n-5) seen.add(n-5) if n+5 in x and n+5 not in seen: q.append(n+5) seen.add(n+5) if set(seen)==set(x):##所有看到过的seen数组里的均联通,若有一个框框与其他的不连通,则seen长度绝对小于原有的x长度 return True else: return Falsecount=0a=[1,2,3,4,6,7,8,9,11,12,13,14]b=list(itertools.combinations(a,5))for i in b: if isLiant(i): count+=1print(count)
转载地址:https://blog.csdn.net/yfuyu/article/details/109540440 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月27日 10时42分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
抖音视频批量去水印,抖音视频批量解析下载方法 - 2020年6月最新有效
2019-04-29
linux下redis安装遇到的问题及解决办法
2019-04-29
历史数据解决方案
2019-04-29
【基础+实战】JVM原理及优化系列之一:JVM体系结构
2019-04-29
【基础+实战】JVM原理及优化系列之二:JVM内存管理
2019-04-29
【基础+实战】JVM原理及优化系列之三:JVM垃圾收集器
2019-04-29
【基础+实战】JVM原理及优化系列之四:JVM参数说明
2019-04-29
【基础+实战】JVM原理及优化系列之五:JVM默认设置
2019-04-29
【基础+实战】JVM原理及优化系列之六:JVM主要调优参数
2019-04-29
【基础+实战】JVM原理及优化系列之十:JVM内存泄漏专题实战
2019-04-29
Redis高可用架构 (redis主从+sentinel)
2019-04-29
【重磅推出】性能提升100倍的性能测试监控优化方法
2019-04-29
Spring cloud微服务框架简介
2019-04-29
【实用】Redis各种存储结构使用场景
2019-04-29
【实用】Redis高级功能
2019-04-29
DevOps八荣八耻了解下,哈哈~
2019-04-29
API Gateway(API网关)介绍
2019-04-29
【免费】少儿编程社区,Scratch中文社区,少儿编程学习交流平台上线~~~
2019-04-29
JavaMail关于使用qq企业邮箱发邮件踩过的坑
2019-04-29