用python实现首先点火数为0有国王和诸侯国王刚开始的烽火是点燃状态使得所有国王可达诸侯进入可见状态点燃状态诸侯不可进入可见状态从可见状态的诸侯挑选出能使让不可见状态的诸侯最大装入可见状态的数量使得这位诸侯进入点燃状态使他的可达诸侯进入可见状态点火数加1重复挑选直到所有诸侯进入可见状态或点燃状态停止挑选输出点火数给出注释
# 定义诸侯和国王的关系,key为国王,value为其可达的诸侯
kingdoms = {
'A': ['B', 'C', 'D'],
'B': ['A', 'C', 'E'],
'C': ['A', 'B', 'D', 'E'],
'D': ['A', 'C'],
'E': ['B', 'C']
}
# 定义点火数和点燃状态的诸侯
fire_count = 0
fired_kingdoms = set(['A'])
while True:
visible_kingdoms = set(fired_kingdoms) # 可见状态的诸侯
invisible_kingdoms = set(kingdoms.keys()) - visible_kingdoms # 不可见状态的诸侯
max_kingdom = None # 能使得不可见状态的诸侯最大装入可见状态的诸侯
max_count = 0 # 能使得不可见状态的诸侯最大装入可见状态的数量
for kingdom in visible_kingdoms:
for neighbor in kingdoms[kingdom]:
if neighbor not in visible_kingdoms and neighbor not in fired_kingdoms:
# 如果邻居不在可见状态或点燃状态中,计算其可见诸侯数量
count = len(set(kingdoms[neighbor]) & visible_kingdoms)
if count > max_count:
max_kingdom = neighbor
max_count = count
if max_kingdom is None: # 如果没有可选的诸侯,则停止挑选
break
fired_kingdoms.add(max_kingdom) # 点燃诸侯
fire_count += 1
print(fire_count)
``
原文地址: https://www.cveoy.top/t/topic/eF2P 著作权归作者所有。请勿转载和采集!