Python 实现烽火传递：最小点火次数算法

以下是用 Python 实现的代码：

def max_visible_lords(lords, lit_lords):
    max_lord = None
    max_count = 0
    for lord in lords:
        if lord in lit_lords:
            continue
        count = 0
        for vassal in lord['vassals']:
            if vassal in lit_lords:
                count += 1
        if count > max_count:
            max_count = count
            max_lord = lord
    return max_lord

def fire(lords):
    lit_lords = set([lord for lord in lords if lord['lit']])
    while len(lit_lords) < len(lords):
        max_lord = max_visible_lords(lords, lit_lords)
        if max_lord is None:
            break
        max_lord['lit'] = True
        for vassal in max_lord['vassals']:
            if vassal not in lit_lords:
                lit_lords.add(vassal)
    return len([lord for lord in lords if lord['lit']])

# Example usage:
lords = [
    {'id': 1, 'vassals': [2, 3], 'lit': True},
    {'id': 2, 'vassals': [4, 5], 'lit': False},
    {'id': 3, 'vassals': [], 'lit': False},
    {'id': 4, 'vassals': [], 'lit': False},
    {'id': 5, 'vassals': [], 'lit': False},
]
print(fire(lords))  # Output: 2

该程序首先定义了一个 max_visible_lords 函数，它接受一个 lords 列表和一个 lit_lords 集合作为参数，返回一个使得可见状态下诸侯最多的诸侯。这个函数的实现就是遍历所有不可见状态的诸侯，对于每个诸侯，计算其可达诸侯中有多少已经点燃，选出可达诸侯最多的诸侯即可。

然后程序定义了一个 fire 函数，它接受一个 lords 列表作为参数，返回点燃所有诸侯的最小次数。这个函数首先将所有点燃状态的诸侯加入到一个集合 lit_lords 中，然后进入一个循环，每次循环找出可见状态下诸侯最多的诸侯，并将其点燃，将其可达诸侯加入到 lit_lords 中。循环直到所有诸侯都点燃或可见状态。

最后程序给出了一个例子，定义了一个包含 5 个诸侯的列表，并将第一个诸侯设为点燃状态，然后调用 fire 函数计算点燃所有诸侯的最小次数，并输出结果。