本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。小蓝要用七段码数码管来表示一种特殊的文字。
上图显示了七段码数码管的图表，共有数码管 7 段能发光的二极管分别标记为 a, b, c, d, e, f, g。小兰应该选择一些二极管（至少一个）来发光来表达字符。在设计字符的表达时，所有发光的二极管都必须连接在一起。 例如：b 发光，其他二极管不发光可以用来表达一个字符。 例如：c 发光，其他二极管不发光可以用来表达一个字符。 这个方案可以用来表示不同的字符，尽管它看起来很相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一个字符。 例如：b, f 如果其他二极管不发光，就不能用来表达一个字符，因为发光的二极管不连接在一起。 请问，小蓝可以用七段码数码管表达多少种不同的字符？ 这是一个填空结果的问题，你只需要结果并提交。 这个问题的结果是一个整数，在提交答案时只填写整数，填写多余的内容将无法得分。
来源：https://www.lanqiao.cn/problems/595/learning/
① 分析题目可以知道，如果题目中所有亮灯都没有连接在一起的条件，那么题目就很简单了，因为每盏灯有两种状态:亮不亮，所以总共有2盏灯。^7=128种，所以当有这种限制时，有必要排除一些不符合主题的情况。递归可以用来解决，因为有两种状态：亮的和不亮的。当确定七盏灯的情况时，有必要判断这些亮灯是否连接在一起。判断是否连接在一起的特点可以知道这是一个连接性的判断问题主要有两种方法，第一种方法是使用搜索判断，连接所有连接节点，第二种是使用判断方法，以下采用并收集的方法进行连通性判断
② 事实上，理解使用和收集判断之间的连通性仍然相对简单，主要涉及两个操作（搜索和合并操作），搜索当前节点x的父节点并合并当前节点x, y父子关系(当x节点的父节点不等于y节点的父节点时)，可以通过递归的方式找到当前节点x的父节点，此外，在查找当前节点的父节点时，可以通过下图清楚地理解根节点向下连接的节点，主要是指向所有具有联系节点的父节点，以便找到最终的父节点。
并收集搜索和合并操作，合并前需要找到当前的两个节点x，y父节点，当father[x] != father[y]合并时，以下是具体代码。事实上，理解后记住它（通常是这样的操作）
def union(self, x: int, y: int, father: List[int]): fa = self.find(x, father) fb = self.find(y, father) if fa != fb: father[fa] = fb return def find(self, x: int, father: List[int]): if x == father[x]: return x father[x] = self.find(father[x], father) return father[x]其实有收集，不同的点主要基于初始化father数组的值不同，第一种写法是初始化father数组是自身位置的值，即father[i] = i。第二种写法在一开始就初始化了一切father全数组值为0。第一种初始化father数组是常规写法，感觉第二种写法会更简单。以下是蓝桥杯合根植物的植物的例子来解释它的初始化father数组都是0，下面的例子可以说明一个长度为20的数组，我们实际上在搜索时输入(1、5)、(5、9)、(9、10)、(10、12)、(12、16)...实际上，左边的联通块修改了1、5、6、10、11、12、16，18的父节点，最后17这个节点的父节点没有修改也就是0，所以可以知道只要是具有联系的两个节点的父节点都是被修改了的，直到到达最后的那个节点，因为最后那个节点没有与其他的节点进行连续了所有父节点是为0的，所以我们最终只需要判断出father连接块的数量可以通过数组中0个节点的数量来知道，用这种方法来判断是非常快速和简单的，只需要在判断开始时声明全部为0father数组，然后找到所有相关的父节点，最后计算father中为0的数量是连通块的数量。
第二种方法实际上是相似的，因为father当数组初始化时father[i] = i，因此，在寻找父节点时，也修改了具有联系节点的父节点。只有最后一个父节点没有修改，最后一个父节点是自己的，所以我们只需要判断父节点是自己的节点，即连接块的数量
③ 事实上，这个话题的一个美妙点是，我们使用二维列表的下标关系来表示灯的连接，我们可以判断灯是否连接在一起
# 连接字母a graph[0][1] = graph[0][5] = 1 # 连接字母b graph[1][0] = graph[1][2] = graph[1][6] = 1 # 连接字母c graph[2][1] = graph[2][6] = graph[2][3] = 1 # 连接字母d graph[3][2] = graph[3][4] = 1 # 连接字母e graph[4][5] = graph[4][3] = graph[4][6] = 1 # 连接字母f graph[5][0] = graph[5][4] = graph[5][6] = 1 # 字母g的连接 graph[6][5] = graph[6][1] = graph[6][2] = graph[6][4] = 1两种不同的初始化father搜索数组的方法也略有不同：
from typing import List import collections class Solution: res = 0 def solve(self, lights: List[int], index: int, graph: List[List[int]]): self.dfs(lights, 0, graph) return self.res # 合并x, y节点 def union(self, x: int, y: int, father: List[int]): fa = self.find(x, father) fb = self.find(y, father) if fa != fb: father[fa] = fb return # 递归查询x节点的父节点 def find(self, x: int, father: List[int]): if x == father[x]: return x father[x] = self.find(father[x], father) return father[x] def dfs(self, lights: List[int], index: int, graph: List[List[int]]): if index == len(lights): father = [i for i in range(7)] t = list() # 使用列表记录所有亮灯的下标，以判断灯的连接， # 只有通过后面，才能通过所有明亮的情况连接 for i in range(7): if lights[i]: t.append(i) for i in range(len(t)): for j in range(i 1, len(t)): # t[i]与t[j]两盏明亮的灯有连接关系，然后合并 if graph[t[i]][t[j]] == 1: self.union(t[i], t[j], father) count = 0 for i in range(len(t)): # 判断当前节点是否为自己，如果是自己，则表示当前节点是最终父节点 if father[t[i]] == t[i]: count = 1 s = "" # 输出灯亮对应的字符串 for i in range(len(lights)): if lights[i] == 1: s = chr(i ord("a")) print(s) # 判断是否只有一个连通块 if count == 1: self.res = 1 return # 现在的灯亮了 lights[index] = 1 self.dfs(lights, index 1, grap)
# 回溯, 令当前灯为不亮
lights[index] = 0
self.dfs(lights, index + 1, graph)
if __name__ == '__main__':
graph = [[0] * 7 for i in range(7)]
graph[0][1] = graph[0][5] = 1
graph[1][0] = graph[1][2] = graph[1][6] = 1
graph[2][1] = graph[2][6] = graph[2][3] = 1
graph[3][2] = graph[3][4] = 1
graph[4][5] = graph[4][3] = graph[4][6] = 1
graph[5][0] = graph[5][4] = graph[5][6] = 1
graph[6][5] = graph[6][1] = graph[6][2] = graph[6][4] = 1
lights = [0] * 7
print(Solution().solve(lights, 0, graph))
from typing import List
import collections
class Solution:
res = 0
def solve(self, lights: List[int], index: int, graph: List[List[int]]):
self.dfs(lights, 0, graph)
return self.res
def union(self, x: int, y: int, father: List[int]):
fa = self.find(x, father)
fb = self.find(y, father)
if fa != fb:
father[fa] = fb
return
def find(self, x: int, father: List[int]):
# 这里判断的是当前节点的父节点是否为0, 因为在一开始的时候就声明了father数组元素全为0
if father[x] == 0: return x
father[x] = self.find(father[x], father)
return father[x]
def dfs(self, lights: List[int], index: int, graph: List[List[int]]):
# 说明七盏灯的情况已经确定好了
if index == len(lights):
father = [0] * 7
t = list()
for i in range(7):
if lights[i]: t.append(i)
for i in range(len(t)):
for j in range(i + 1, len(t)):
if graph[t[i]][t[j]] == 1:
self.union(t[i], t[j], father)
# print(father)
count = 0
for i in range(len(t)):
if father[t[i]] == 0: count += 1
s = ""
for i in range(len(lights)):
if lights[i] == 1:
s += chr(i + ord("a"))
if count == 1:
self.res += 1
return
lights[index] = 1
self.dfs(lights, index + 1, graph)
lights[index] = 0
self.dfs(lights, index + 1, graph)
if __name__ == '__main__':
graph = [[0] * 7 for i in range(7)]
graph[0][1] = graph[0][5] = 1
graph[1][0] = graph[1][2] = graph[1][6] = 1
graph[2][1] = graph[2][6] = graph[2][3] = 1
graph[3][2] = graph[3][4] = 1
graph[4][5] = graph[4][3] = graph[4][6] = 1
graph[5][0] = graph[5][4] = graph[5][6] = 1
graph[6][5] = graph[6][1] = graph[6][2] = graph[6][4] = 1
lights = [0] * 7
print(Solution().solve(lights, 0, graph))