AcWing 190. 字串变换 python写法
原题链接
中等
作者:
思念聚成海
,
2021-12-13 20:59:28
,
所有人可见
,
阅读 283
一开始吃了TLE,原来是相等的情况没特判
# 双向广搜
from collections import deque
start,end = input().split()
a =[]; b = []
while True:
try:
l,r = input().split()
a.append(l); b.append(r)
except: break
def extend(q,mt1,mt2,at,bt):
cur = q.popleft()
for i in range(len(cur)):
for j in range(len(at)):
if cur[i:i+len(at[j])] == at[j]:
next = cur[:i] + bt[j] + cur[i+len(at[j]):]
if next in mt2: return mt1[cur] + 1 + mt2[next]
if next in mt1: continue
mt1[next] = mt1[cur] + 1
q.append(next)
return 11
def bfs(start,end):
if start == end: return 0
q1 = deque([start]); q2 = deque([end])
m1 = {}; m2 = {}
m1[start] = m2[end] = 0
while q1 and q2:
if len(q1) <= len(q2): t = extend(q1,m1,m2,a,b)
else: t = extend(q2,m2,m1,b,a)
if t <= 10: return t
return 11
ans = bfs(start,end)
print(ans) if ans <= 10 else print('NO ANSWER!')