E=enumerate
L=len
def f(b):
 q,F=[{(x,y):v for x,r in E(b)for y,v in E(r)}],[]
 for d in q:
  O={}
  for i in d:
   if~-(d[i]in'oO0 '):O[d[i]]=O.get(d[i],[])+[i]
  if{}==O:return L(F+[i for i in d if d[i]in'oO0'])
  Q,S,W=[[i]for i in O[[*O][0]]],[],[]
  for p in Q:
   for X,Y in(0,1),(1,0),(-1,0),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1):
    if d.get(V:=(p[-1][0]+X,p[-1][1]+Y))in[d[p[0]],' ']:
     if V==p[0]and L(p)>2:W+=p,
     elif(V in p)<1-((G:=sorted(Z:=p+[V]))in S):Q+=Z,;S+=G,
  if W:
   Q,T=[(W,[])],[]
   for w,P in Q:
    for i,j in E(w):C=P+[j];z=sum(map(L,l:=[{i for i in j if' '!=d[i]}for j in C]))==L({j for k in l for j in k});T+=z*[C];Q+=z*[(w[:i]+w[i+1:],C)]
   F+=max(T or W,key=L)
  for u in O[[*O][0]]:del d[u]
  q+=d,
 
def to_grid(s):
	return [[*i] for i in filter(None, s.split('\n'))]
 
s1 = """
AAAw
AxA4
'AoQ
"""
s2 = """
1822uaslkoo
12*2sl ljoo
a* 0a91)j$*
()*#J9dddj*
*Q#ID dJj!"
*UJD SO&*93
"""
s3 = """
3  3
  2 
"""
s4 = """
AAAA
AAAA
AAxA
"""
s5 = """
0QoO
"""
s6 = """
W w
 Ww
"""
s7 = """
W W
 WW
"""
s8 = """
abcdQefg
hQiQjQQk
QlQmnopQ
QqrstQQu
QvQQQwxy
zQ012QQQ
"""
print(f(to_grid(s1)))
print(f(to_grid(s2)))
print(f(to_grid(s3)))
print(f(to_grid(s4)))
print(f(to_grid(s5)))
print(f(to_grid(s6)))
print(f(to_grid(s7)))
print(f(to_grid(s8)))

RT1lbnVtZXJhdGUKTD1sZW4KZGVmIGYoYik6CiBxLEY9W3soeCx5KTp2IGZvciB4LHIgaW4gRShiKWZvciB5LHYgaW4gRShyKX1dLFtdCiBmb3IgZCBpbiBxOgogIE89e30KICBmb3IgaSBpbiBkOgogICBpZn4tKGRbaV1pbidvTzAgJyk6T1tkW2ldXT1PLmdldChkW2ldLFtdKStbaV0KICBpZnt9PT1POnJldHVybiBMKEYrW2kgZm9yIGkgaW4gZCBpZiBkW2ldaW4nb08wJ10pCiAgUSxTLFc9W1tpXWZvciBpIGluIE9bWypPXVswXV1dLFtdLFtdCiAgZm9yIHAgaW4gUToKICAgZm9yIFgsWSBpbigwLDEpLCgxLDApLCgtMSwwKSwoMCwtMSksKDEsMSksKC0xLDEpLCgxLC0xKSwoLTEsLTEpOgogICAgaWYgZC5nZXQoVjo9KHBbLTFdWzBdK1gscFstMV1bMV0rWSkpaW5bZFtwWzBdXSwnICddOgogICAgIGlmIFY9PXBbMF1hbmQgTChwKT4yOlcrPXAsCiAgICAgZWxpZihWIGluIHApPDEtKChHOj1zb3J0ZWQoWjo9cCtbVl0pKWluIFMpOlErPVosO1MrPUcsCiAgaWYgVzoKICAgUSxUPVsoVyxbXSldLFtdCiAgIGZvciB3LFAgaW4gUToKICAgIGZvciBpLGogaW4gRSh3KTpDPVArW2pdO3o9c3VtKG1hcChMLGw6PVt7aSBmb3IgaSBpbiBqIGlmJyAnIT1kW2ldfWZvciBqIGluIENdKSk9PUwoe2ogZm9yIGsgaW4gbCBmb3IgaiBpbiBrfSk7VCs9eipbQ107USs9eipbKHdbOmldK3dbaSsxOl0sQyldCiAgIEYrPW1heChUIG9yIFcsa2V5PUwpCiAgZm9yIHUgaW4gT1tbKk9dWzBdXTpkZWwgZFt1XQogIHErPWQsCiAgCmRlZiB0b19ncmlkKHMpOgoJcmV0dXJuIFtbKmldIGZvciBpIGluIGZpbHRlcihOb25lLCBzLnNwbGl0KCdcbicpKV0KCnMxID0gIiIiCkFBQXcKQXhBNAonQW9RCiIiIgpzMiA9ICIiIgoxODIydWFzbGtvbwoxMioyc2wgbGpvbwphKiAwYTkxKWokKgooKSojSjlkZGRqKgoqUSNJRCBkSmohIgoqVUpEIFNPJio5MwoiIiIKczMgPSAiIiIKMyAgMwogIDIgCiIiIgpzNCA9ICIiIgpBQUFBCkFBQUEKQUF4QQoiIiIKczUgPSAiIiIKMFFvTwoiIiIKczYgPSAiIiIKVyB3CiBXdwoiIiIKczcgPSAiIiIKVyBXCiBXVwoiIiIKczggPSAiIiIKYWJjZFFlZmcKaFFpUWpRUWsKUWxRbW5vcFEKUXFyc3RRUXUKUXZRUVF3eHkKelEwMTJRUVEKIiIiCnByaW50KGYodG9fZ3JpZChzMSkpKQpwcmludChmKHRvX2dyaWQoczIpKSkKcHJpbnQoZih0b19ncmlkKHMzKSkpCnByaW50KGYodG9fZ3JpZChzNCkpKQpwcmludChmKHRvX2dyaWQoczUpKSkKcHJpbnQoZih0b19ncmlkKHM2KSkpCnByaW50KGYodG9fZ3JpZChzNykpKQpwcmludChmKHRvX2dyaWQoczgpKSk=