faililaud=list(map(lambda rida: rida.strip(), open("laud.txt").readlines()))
ridu=len(faililaud)
veerge=len(faililaud[0])
k2igud={}

for rida in range(ridu):
  for veerg in range(veerge):
    if faililaud[rida][veerg]=='S': start=[rida, veerg]
    elif faililaud[rida][veerg]=='F': finis=[rida, veerg]
    
def leiaK2igud(koht): #sisendiks kuubiku asukoht arvumassiivina
  v=[]
  if len(koht)==2: #kui on pysti
     v.append([koht[0], koht[1]+1, koht[0], koht[1]+2]) #paremale
     v.append([koht[0], koht[1]-2, koht[0], koht[1]-1]) #vasakule
     v.append([koht[0]-2, koht[1], koht[0]-1, koht[1]]) #yles
     v.append([koht[0]+1, koht[1], koht[0]+2, koht[1]]) #alla
  if len(koht)==4:
     if koht[0]==koht[2]: 
        v.append([koht[0]-1, koht[1], koht[2]-1, koht[3]]) #yles
        v.append([koht[0]+1, koht[1], koht[2]+1, koht[3]]) #alla
        v.append([koht[0], koht[1]-1]) #vasakule pysti
        v.append([koht[0], koht[3]+1]) #paremale pysti
     if koht[1]==koht[3]:
        v.append([koht[0], koht[1]-1, koht[2], koht[3]-1]) #vasakule
        v.append([koht[0], koht[1]+1, koht[2], koht[3]+1]) #paremale
        v.append([koht[0]-1, koht[1]]) #yles pysti
        v.append([koht[2]+1, koht[3]]) #alla pysti
     #Lisage k2igud ka samas veerus pikali oleva ploki kohta
  return v
  
def kasVaba(rida, veerg):
  return rida in range(ridu) and veerg in range(veerge) and \
     faililaud[rida][veerg]!="X"
     
def kasSobib(asukoht):
   if len(asukoht)==2: return kasVaba(asukoht[0], asukoht[1])
   if len(asukoht)==4: return kasVaba(asukoht[0], asukoht[1]) and \
     kasVaba(asukoht[2], asukoht[3])
  
def sobivadK2igud(koht):
     return list(filter(kasSobib, leiaK2igud(koht)))

def r2si(koht):
    return "-".join(map(str, koht))    
uuritavad=[start]
tagasitee={r2si(start) : start}
while uuritavad:
  uuritav=uuritavad.pop(0)
  for koht in sobivadK2igud(uuritav): 
    if r2si(koht) not in tagasitee:
      tagasitee[r2si(koht)]=uuritav
      uuritavad.append(koht)      

print(tagasitee)
if r2si(finis) in tagasitee:
  teekond=[finis]
  koht=finis
  while not koht==start:
    koht=tagasitee[r2si(koht)]
    teekond.append(koht)
print(teekond)