E=enumerate
def f(b):
 d={}
 for x,r in E(b):
  for y,v in E(r):d[v]=d.get(v,[])+[(x,y)]
 S=lambda:[(T:=[*{*d}-{'-'}][0],*(l:=d.pop(T))[0],*({*l}-{l[0]}),{**d},eval(str(b)))];q=S()
 while q:
  C,x,y,e,d,b=q.pop(0)
  for T in(x,y+1),(x,y-1),(x+1,y),(x-1,y):
   if T in d['-']:B=eval(str(b));B[T[0]][T[1]]=C;q+=(C,*T,e,{**d,'-':{*d['-']}-{T}},B),
   elif T==e:
    if(z:=len(d))==1and not d['-']:return b
    if z>1:q+=S()
 
s1 = """
-ABCD
-A---
---C-
---BD
--E-E
"""
s2 = """
E--E-
BB-C-
AD---
---C-
AD---
"""
 
s3 ="""
A----
---B-
-C-C-
-D-D-
BE-EA
"""
 
def to_board(s):
	return [[*i] for i in filter(None, s.split('\n'))]
 
def F(s):
	return '\n'.join(map(''.join, f(to_board(s))))
 
print(F(s1))
print('-'*20)
print(F(s2))
print('-'*20)
print(F(s3))

RT1lbnVtZXJhdGUKZGVmIGYoYik6CiBkPXt9CiBmb3IgeCxyIGluIEUoYik6CiAgZm9yIHksdiBpbiBFKHIpOmRbdl09ZC5nZXQodixbXSkrWyh4LHkpXQogUz1sYW1iZGE6WyhUOj1bKnsqZH0teyctJ31dWzBdLCoobDo9ZC5wb3AoVCkpWzBdLCooeypsfS17bFswXX0pLHsqKmR9LGV2YWwoc3RyKGIpKSldO3E9UygpCiB3aGlsZSBxOgogIEMseCx5LGUsZCxiPXEucG9wKDApCiAgZm9yIFQgaW4oeCx5KzEpLCh4LHktMSksKHgrMSx5KSwoeC0xLHkpOgogICBpZiBUIGluIGRbJy0nXTpCPWV2YWwoc3RyKGIpKTtCW1RbMF1dW1RbMV1dPUM7cSs9KEMsKlQsZSx7KipkLCctJzp7KmRbJy0nXX0te1R9fSxCKSwKICAgZWxpZiBUPT1lOgogICAgaWYoejo9bGVuKGQpKT09MWFuZCBub3QgZFsnLSddOnJldHVybiBiCiAgICBpZiB6PjE6cSs9UygpCiAgICAKczEgPSAiIiIKLUFCQ0QKLUEtLS0KLS0tQy0KLS0tQkQKLS1FLUUKIiIiCnMyID0gIiIiCkUtLUUtCkJCLUMtCkFELS0tCi0tLUMtCkFELS0tCiIiIgoKczMgPSIiIgpBLS0tLQotLS1CLQotQy1DLQotRC1ELQpCRS1FQQoiIiIKCmRlZiB0b19ib2FyZChzKToKCXJldHVybiBbWyppXSBmb3IgaSBpbiBmaWx0ZXIoTm9uZSwgcy5zcGxpdCgnXG4nKSldCgpkZWYgRihzKToKCXJldHVybiAnXG4nLmpvaW4obWFwKCcnLmpvaW4sIGYodG9fYm9hcmQocykpKSkKCnByaW50KEYoczEpKQpwcmludCgnLScqMjApCnByaW50KEYoczIpKQpwcmludCgnLScqMjApCnByaW50KEYoczMpKQ==