本文共 1301 字，大约阅读时间需要 4 分钟。

蓝桥python—— 剪邮票【2016 第七题】

题目描述 如【图 1.jpg】, 有 12 张连在一起的 12 生肖的邮票。 现在你要从中剪下 5 张来，要求必须 是连着的。 （仅仅连接一个角不算相连） 比如，【图 2.jpg】，【图 3.jpg】中，粉红色所 示部分就是合格的剪取。

先给大家说下这个题目拿过来我的思路吧

python的话从12个框框中选5个很简单，即调用itertools.combinations函数（记住是组合而不是排列）

但是要判断是否联通，对于两个框框肯定是相邻的，题目上标注的数字的话则是两个框框之差绝对值为1或者4！可是有个问题，就是绝对值为1的不一定相邻，比如 8 9

因此我们可以把以上的图变（想成）为下面的

在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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！