蓝桥python—— 剪邮票【2016 第七题】 【蓝桥杯|蓝桥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 False
count=0
a=[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+=1
print(count)推荐阅读
- 备战蓝桥杯|【蓝桥python冲刺17天】——如何轻松拿捏必考数论题（（第三弹））
- 备战蓝桥杯|【蓝桥python冲刺31天】——如何轻松拿捏必考数论题（（第一弹））
- #|python opencv 图像像素处理基础
- 神经网络|【论文导读】浅谈胶囊网络与动态路由算法
- 图像处理与机器视觉|LM算法
- Python科学计算和数据分析|Seaborn系列(五)（回归(Regression)及矩阵(Matrix)绘图）
- 10行代码实现一个值班提醒应用
- 用Markdown写邮件，用Python发邮件
- ffmpeg|bilibili缓存视频批量转换成mp4格式，方便学习