laud=[list(rida) for rida in open("sisend1.txt").read().split("\n")]
def tryki():
  print("\n".join(["".join(rida) for rida in laud]))

for reanr in range(8):
  for veerunr in range(8):
     if laud[reanr][veerunr]=="R": 
        alguskoht=(reanr, veerunr)
        laud[reanr][veerunr]='.'
     if laud[reanr][veerunr]=="K": 
        sihtkoht=(reanr, veerunr)
        laud[reanr][veerunr]='.'
print(laud)
tryki()
kaigud=[[-1,-2], [-1, 2], [-2, 1], [-2, -1], 
        [ 1,-2], [-1,-2], [ 2, 1], [ 2, -1]]
def nihe(koht, samm): return (koht[0]+samm[0], koht[1]+samm[1])
def vaartus(koht): return laud[koht[0]][koht[1]]
def kasVaba(koht): return kasSees(koht) and vaartus(koht)=='.'
def kasSees(koht): return 0<=koht[0]<=7 and 0<=koht[1]<=7
def sammud(koht): return [tuple(nihe(koht, kaik)) 
           for kaik in kaigud if kasVaba(nihe(koht, kaik))]

leitud=[alguskoht]
tagasitee={tuple(alguskoht): None}
while leitud:
   uuritav=leitud.pop(0)
   for koht in sammud(uuritav):
     if koht not in tagasitee:
      tagasitee[koht]=uuritav
      leitud.append(koht)
print(tagasitee)
#Teatage, kas sihtkohta pääseb
#print("saab" if sihtkoht in tagasitee else "ei saa")
if sihtkoht in tagasitee:
  koht=sihtkoht
  while koht!=None:
    print(koht)
    laud[koht[0]][koht[1]]='*'
    koht=tagasitee[koht]

tryki()