python如何实现成语接龙的最小路径问题?

Question

问题很简单,在给出的成语中,在能够接龙的前提下,找到成语的最短路径,每个成语只能使用一次,接龙即:前一个成语的最后一个字和后一个成语的最后一个字相同,最短路径即 组成接龙的成语数量最少

Answer 1

把成语放到字典中成语的第一个字作为字典的键，用广度优先方式遍历就好
你题目的解答代码如下：（如有帮助，望采纳！谢谢! 点击我这个回答右上方的【采纳】按钮）

st = input("请输入成语中接龙的起始字：")
et = input("请输入成语中接龙的结束字：")
li = input("请输入多个成语(以空格分隔)：").split(" ")
def jl(li,st,et):
    dic = {}
    for v in li:
        dic.setdefault(v[0],[]).append(v)
    r = {st:[]}
    while len(r)>0:
        tr = {}
        for k,v in r.items():
            if k in dic:
                for c in dic[k]:
                    if c not in v:
                        tr[c[-1]] = v + [c]
                        if c[-1]==et:
                            return tr[c[-1]]
        r = tr
    return "无法接龙"

print(jl(li,st,et))