用python实现首先点火数为0有国王和诸侯国王刚开始的烽火是点燃状态使得所有国王可达诸侯进入可见状态点燃状态诸侯不可进入可见状态从可见状态的诸侯挑选出能使让不可见状态的诸侯最大装入可见状态的数量使得这位诸侯进入点燃状态使他的可达诸侯进入可见状态点火数加1重复挑选直到所有诸侯进入可见状态或点燃状态停止挑选输出点火数
以下是用Python实现的代码:
def find_max_visible(lords, visible):
max_visible = 0
max_lord = None
for lord in lords:
if lord in visible:
continue
visible_lords = set()
for v in visible:
if lord in v.reachable:
visible_lords.add(v)
if len(visible_lords) > max_visible:
max_visible = len(visible_lords)
max_lord = lord
return max_lord
class Lord:
def __init__(self, name):
self.name = name
self.reachable = set()
def __str__(self):
return self.name
class VisibleLord:
def __init__(self, lord):
self.lord = lord
self.reachable = lord.reachable
def __str__(self):
return str(self.lord)
def fire(lords, king):
visible = set()
visible.add(VisibleLord(king))
fire_count = 0
while len(visible) < len(lords):
lord = find_max_visible(lords, visible)
visible_lords = set()
for v in visible:
if v.lord in lord.reachable:
visible_lords.add(v)
visible_lords.add(VisibleLord(lord))
visible.update(visible_lords)
lord.reachable.add(lord)
for v in visible_lords:
v.lord.reachable.update(lord.reachable)
fire_count += 1
return fire_count
# Example usage:
lords = [Lord('A'), Lord('B'), Lord('C'), Lord('D'), Lord('E'), Lord('F')]
lords[0].reachable.update([lords[1], lords[2]])
lords[1].reachable.update([lords[2], lords[3]])
lords[2].reachable.update([lords[3]])
lords[3].reachable.update([lords[4]])
lords[4].reachable.update([lords[5]])
king = lords[0]
king_reachable = set()
for lord in lords:
if lord in king.reachable:
king_reachable.add(lord)
visible_lords = set()
for lord in king_reachable:
visible_lords.add(VisibleLord(lord))
visible_lords.add(VisibleLord(king))
visible = set(visible_lords)
for v in visible_lords:
v.lord.reachable.update(king_reachable)
fire_count = fire(lords, king)
print(f'Fire count: {fire_count}')
这里使用了两个类,Lord表示诸侯,VisibleLord表示可见状态的诸侯。Lord对象包含一个reachable属性,表示可以到达的其他Lord对象。VisibleLord对象包含一个lord属性,表示对应的Lord对象,以及一个reachable属性,表示可以到达的其他Lord对象。在fire函数中,根据当前可见状态的诸侯,寻找能够使得不可见状态的诸侯最大装入可见状态的数量的诸侯,并将其加入可见状态,直到所有诸侯进入可见状态或点燃状态为止
原文地址: https://www.cveoy.top/t/topic/eF2s 著作权归作者所有。请勿转载和采集!