E=enumerate
M=[(1,0),(0,1),(-1,0),(0,-1)]
def P(x,y,t,d):
 q=[(x,y,[])]
 for x,y,s in q:
  if(x,y)in t:return s[:-1]
  for X,Y in M:q+=((0==d.get(U:=(x+X,y+Y))or U in t)*~-(U in s)*~-any(all((x+X,y+Y)in s+[U]+t for X,Y in[(0,0),(1,1)]+M[:2])for x,y in s+[U]+t))*[(*U,s+[U])]
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)};a,b,*r=[i for i in d if d[i]];p=P(*a,[b],d)
 while r:p+=P(*r.pop(),p,d)
 return p
 
def to_board(s):
	return [[int(j=='k')for j in i]for i in filter(None, s.split('\n'))]
 
def display_solution(s,p):
	s=[*map(list,filter(None, s.split('\n')))]
	for x, y in p:s[x][y]= '#'
	print('\n'.join(''.join(i) for i in s))
 
s1 = """
.........
....k....
.........
.........
.k.......
.........
.....k...
.........
.........
"""
s2 = """
k.k......
.........
k........
.........
.........
.........
.........
.........
.........
"""
s3 = """
.k.......
k........
.k.......
.........
.........
.........
.........
.........
.........
"""
s4 ="""
.........
.........
k........
.........
k........
.........
k........
.........
.........
"""
s5 = """
........k
....k....
.........
.........
.........
.........
.........
....k....
.........
"""
s6 = """
.........
.........
.........
.........
.........
.........
k........
.k.......
..k......
"""
display_solution(s1, f(to_board(s1)))
print('-'*40)
display_solution(s2, f(to_board(s2)))
print('-'*40)
display_solution(s3, f(to_board(s3)))
print('-'*40)
display_solution(s4, f(to_board(s4)))
print('-'*40)
display_solution(s5, f(to_board(s5)))
print('-'*40)
display_solution(s6, f(to_board(s6)))

RT1lbnVtZXJhdGUKTT1bKDEsMCksKDAsMSksKC0xLDApLCgwLC0xKV0KZGVmIFAoeCx5LHQsZCk6CiBxPVsoeCx5LFtdKV0KIGZvciB4LHkscyBpbiBxOgogIGlmKHgseSlpbiB0OnJldHVybiBzWzotMV0KICBmb3IgWCxZIGluIE06cSs9KCgwPT1kLmdldChVOj0oeCtYLHkrWSkpb3IgVSBpbiB0KSp+LShVIGluIHMpKn4tYW55KGFsbCgoeCtYLHkrWSlpbiBzK1tVXSt0IGZvciBYLFkgaW5bKDAsMCksKDEsMSldK01bOjJdKWZvciB4LHkgaW4gcytbVV0rdCkpKlsoKlUscytbVV0pXQpkZWYgZihiKToKIGQ9eyh4LHkpOnYgZm9yIHgsciBpbiBFKGIpZm9yIHksdiBpbiBFKHIpfTthLGIsKnI9W2kgZm9yIGkgaW4gZCBpZiBkW2ldXTtwPVAoKmEsW2JdLGQpCiB3aGlsZSByOnArPVAoKnIucG9wKCkscCxkKQogcmV0dXJuIHAKIApkZWYgdG9fYm9hcmQocyk6CglyZXR1cm4gW1tpbnQoaj09J2snKWZvciBqIGluIGldZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMuc3BsaXQoJ1xuJykpXQoKZGVmIGRpc3BsYXlfc29sdXRpb24ocyxwKToKCXM9WyptYXAobGlzdCxmaWx0ZXIoTm9uZSwgcy5zcGxpdCgnXG4nKSkpXQoJZm9yIHgsIHkgaW4gcDpzW3hdW3ldPSAnIycKCXByaW50KCdcbicuam9pbignJy5qb2luKGkpIGZvciBpIGluIHMpKQoKczEgPSAiIiIKLi4uLi4uLi4uCi4uLi5rLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi5rLi4uLi4uLgouLi4uLi4uLi4KLi4uLi5rLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KIiIiCnMyID0gIiIiCmsuay4uLi4uLgouLi4uLi4uLi4Kay4uLi4uLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCiIiIgpzMyA9ICIiIgouay4uLi4uLi4Kay4uLi4uLi4uCi5rLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgoiIiIKczQgPSIiIgouLi4uLi4uLi4KLi4uLi4uLi4uCmsuLi4uLi4uLgouLi4uLi4uLi4Kay4uLi4uLi4uCi4uLi4uLi4uLgprLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgoiIiIKczUgPSAiIiIKLi4uLi4uLi5rCi4uLi5rLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi5rLi4uLgouLi4uLi4uLi4KIiIiCnM2ID0gIiIiCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCi4uLi4uLi4uLgouLi4uLi4uLi4KLi4uLi4uLi4uCmsuLi4uLi4uLgouay4uLi4uLi4KLi5rLi4uLi4uCiIiIgpkaXNwbGF5X3NvbHV0aW9uKHMxLCBmKHRvX2JvYXJkKHMxKSkpCnByaW50KCctJyo0MCkKZGlzcGxheV9zb2x1dGlvbihzMiwgZih0b19ib2FyZChzMikpKQpwcmludCgnLScqNDApCmRpc3BsYXlfc29sdXRpb24oczMsIGYodG9fYm9hcmQoczMpKSkKcHJpbnQoJy0nKjQwKQpkaXNwbGF5X3NvbHV0aW9uKHM0LCBmKHRvX2JvYXJkKHM0KSkpCnByaW50KCctJyo0MCkKZGlzcGxheV9zb2x1dGlvbihzNSwgZih0b19ib2FyZChzNSkpKQpwcmludCgnLScqNDApCmRpc3BsYXlfc29sdXRpb24oczYsIGYodG9fYm9hcmQoczYpKSk=