E=enumerate
M=(0,1),(1,0),(-1,0),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)
m,g,p='MF.'
def f(F):
 q,s=[({(x,y):v for x,r in E(F)for y,v in E(r)},0)],[]
 for d,C in q:
  R=Q=[(d,0)];T=[]
  for D,c in Q:
   if~c%2:
    [v]=[i for i in D if m==D[i]]
    for X,Y in M:
     if-1==D.get(V:=(v[0]+X,v[1]+Y),-1):R=0
     elif(g!=D[V])>((U:={**D,v:p,V:m})in T):Q+=(U,c+1),;T+=U,
   else:S=[V for v in D for X,Y in M if g==D[v]and D.get(V:=(v[0]+X,v[1]+Y),-1)in[m,p]];Q+=[({**D,**{i:g for i in S if p==D[i]}},c+1)]*all(m!=D[i]for i in S)
  if R:return C 
  for i in d:
   if(p==d[i])>((U:={**d,i:g})in s):q+=(U,C+1),;s+=U,
 
def to_board(s):
	return [[*i] for i in filter(None, s.split('\n'))]
s = """
FFFFF
F...F
F.M.F
F...F
FFFFF
"""
s1 = """
FFFFF
F....
F....
F....
F.M..
F....
F....
F....
FFFFF
"""
s2 = """
.....
.....
..M..
.....
.....
"""
print(f(to_board(s)))
print(f(to_board(s1)))
print(f(to_board(s2)))

RT1lbnVtZXJhdGUKTT0oMCwxKSwoMSwwKSwoLTEsMCksKDAsLTEpLCgxLDEpLCgtMSwxKSwoMSwtMSksKC0xLC0xKQptLGcscD0nTUYuJwpkZWYgZihGKToKIHEscz1bKHsoeCx5KTp2IGZvciB4LHIgaW4gRShGKWZvciB5LHYgaW4gRShyKX0sMCldLFtdCiBmb3IgZCxDIGluIHE6CiAgUj1RPVsoZCwwKV07VD1bXQogIGZvciBELGMgaW4gUToKICAgaWZ+YyUyOgogICAgW3ZdPVtpIGZvciBpIGluIEQgaWYgbT09RFtpXV0KICAgIGZvciBYLFkgaW4gTToKICAgICBpZi0xPT1ELmdldChWOj0odlswXStYLHZbMV0rWSksLTEpOlI9MAogICAgIGVsaWYoZyE9RFtWXSk+KChVOj17KipELHY6cCxWOm19KWluIFQpOlErPShVLGMrMSksO1QrPVUsCiAgIGVsc2U6Uz1bViBmb3IgdiBpbiBEIGZvciBYLFkgaW4gTSBpZiBnPT1EW3ZdYW5kIEQuZ2V0KFY6PSh2WzBdK1gsdlsxXStZKSwtMSlpblttLHBdXTtRKz1bKHsqKkQsKip7aTpnIGZvciBpIGluIFMgaWYgcD09RFtpXX19LGMrMSldKmFsbChtIT1EW2ldZm9yIGkgaW4gUykKICBpZiBSOnJldHVybiBDIAogIGZvciBpIGluIGQ6CiAgIGlmKHA9PWRbaV0pPigoVTo9eyoqZCxpOmd9KWluIHMpOnErPShVLEMrMSksO3MrPVUsCiAgIApkZWYgdG9fYm9hcmQocyk6CglyZXR1cm4gW1sqaV0gZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMuc3BsaXQoJ1xuJykpXQpzID0gIiIiCkZGRkZGCkYuLi5GCkYuTS5GCkYuLi5GCkZGRkZGCiIiIgpzMSA9ICIiIgpGRkZGRgpGLi4uLgpGLi4uLgpGLi4uLgpGLk0uLgpGLi4uLgpGLi4uLgpGLi4uLgpGRkZGRgoiIiIKczIgPSAiIiIKLi4uLi4KLi4uLi4KLi5NLi4KLi4uLi4KLi4uLi4KIiIiCnByaW50KGYodG9fYm9hcmQocykpKQpwcmludChmKHRvX2JvYXJkKHMxKSkpCnByaW50KGYodG9fYm9hcmQoczIpKSk=