【問題描述】
小藍要用七段碼數碼管來表示一種特殊的文字，
上圖給出了七段碼數碼管的一個圖示，數碼管中一共有 7 段可以發光的二極管，分別標記為 a, b, c, d, e, f, g，
小藍要選擇一部分二極管（至少要有一個）發光來表達字符，
在設計字符的表達時，要求所有發光的二極管是連成一片的，
例如：b 發光，其他二極管不發光可以用來表達一種字符，
例如：c 發光，其他二極管不發光可以用來表達一種字符，
這種方案與上一行的方案可以用來表示不同的字符，盡管看上去比較相似，
例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字符，
例如：b, f 發光，其他二極管不發光則不能用來表達一種字符，因為發光的二極管沒有連成一片，
請問，小藍可以用七段碼數碼管表達多少種不同的字符？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，
本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
解題：并查集+深搜
（答案不對但看不出哪錯了）
from string import ascii_letters
from itertools import combinations
from collections import deque
class UF:
def __init__(self, count, ori: tuple):
self.res = 0
self.count = count
self.lst = []
self.deque = deque(ori)
self.parent = {
'a': ['b', 'f'],
'b': ['a', 'g', 'c'],
'c': ['b', 'd', 'g'],
'd': ['c', 'd'],
'e': ['d', 'f', 'g'],
'f': ['a', 'e', 'g'],
'g': ['b', 'c', 'e', 'f']
}
def union(self, x):
if self.lst:
for node in self.lst:
if x in self.parent[node]:
self.lst.append(x)
return True
else:
return False
else:
self.lst.append(x)
return True
def func(self):
length = self.count
while True:
count = 0
while count < length:
x = self.deque.popleft()
if self.union(x):
pass
else:
self.deque.append(x)
count += 1
if length == len(self.deque):
break
else:
length = len(self.deque)
if not self.deque:
break
if len(self.deque) == 0:
return True
if __name__ == '__main__':
str_lst = list(ascii_letters[:7])
count = 0
for i in range(1, 8):
for choice in combinations(str_lst, i):
uf = UF(i, choice)
if uf.func():
count += 1
print(i, count)
print(count)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257463.html
標籤：python