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

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

题目描述 如【图 1.jpg】, 有 12 张连在一起的 12 生肖的邮票。 现在你要从中剪下 5 张来,要求必须 是连着的。 (仅仅连接一个角不算相连) 比如,【图 2.jpg】,【图 3.jpg】中,粉红色所 示部分就是合格的剪取。
请你计算,一共有多少种不同的剪取方法。 请填写表示方案数目的整数。 注意:你提交的应该是一个整数,不要填写任何多余的内容 或说明性文字。

蓝桥python—— 剪邮票【2016 第七题】先给大家说下这个题目拿过来我的思路吧
首先题目的意思是有12个框框,我们要选择5个框框,再来判断是否连通,若联通,则答案加1

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

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

因此我们可以把以上的图变(想成)为下面的蓝桥python—— 剪邮票【2016 第七题】
说明:改数字对结果毫无影响,只是让我们更好判断是否连通
显然我们看到 只要两个框框之差绝对值为 1或者5 就一定相邻

在12个框框中选择5个后,我们用bfs算法判断这个5个框框是否连通

代码如下

import itertools

def 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)

匿名

发表评论

匿名网友