f=\
lambda b:M(set(),b,0,2,[],(0,0))
Z=max
W=min
L={0:Z,2:W}
K={0:W,2:Z}
T={0:L,1:K,2:K,3:L}
Q={0:(0,1),1:(1,0),2:(0,-1),3:(-1,0)}
I={0:lambda s,v,*a:[*a,[v]+s],1:lambda s,v,*a:[*a,s[1:]],2:lambda s,v,*a:[*a,[sum(s[:2])]+s[2:]],3:lambda s,v,*a:[*a,[s[1]-s[0]]+s[2:]],4:lambda s,v,*a:[*a,[s[0]*s[1]]+s[2:]],5:lambda s,v,*a:[*a,[s[1]/s[0]]+s[2:]],6:lambda s,v,u,q:[[u,q,s],[s[0]+u&3,q,s[1:]]][[]<s],7:lambda s,v,u,q:[u,s[0]%2*2,s[1:]]}
def V(b,x,y):
 try:return b[x][y]!=9and x>-1<y
 except:return 0
def C(b,v,s):
 q,S,D,d=[s],[s],{s[0]:[s[1]]},{s[1]:[s[0]]}
 while q:
  x,y=q.pop(0)
  for n,m in Q.values():
   try:
    if(X:=x+n)>-1<(Y:=y+m)and~-((X,Y)in S)and b[X][Y]==v:q+=(X,Y),;S+=(X,Y),;D[X]=D.get(X,[])+[Y];d[Y]=d.get(Y,[])+[X]
   except:1
 return S,D,d
def M(H,b,u,q,s,c,P=0,E=[]):
 if(_:=str([u,q,s,c,P,E,b[c[0]][c[1]]]))in H:return s
 H.add(_);x,*y=C(b,S:=b[c[0]][c[1]],c)
 if P==8:return s
 if S-8:
  if u in[0,2]:Y=[Z,W][u>0](y[1]);X=T[u][q](y[1][Y])
  else:X=[Z,W][u==3](y[0]);Y=T[u][q](y[0][X])
 else:X,Y=c
 return M(H,b,*(I[b[A][B]](s,len(x),u,q)if b[A][B]in I and(s or b[A][B]<2)else[u,q,s]),(A,B),0,[])if V(b,A:=X+Q[u][0],B:=Y+Q[u][1])else S-8and M(H,b,[u,-~u%4][P%2],[2*(q<1),q][P%2],s,(X,Y),P+1,[])or M(H,b,-~u%4,2*(q<1),s,(X,Y),0,E+[(X,Y)])
 
prog ="""
111090908004
911088808944
911069912399
"""
prog1="""
1199999999999999
9890888898889889
8880888000888808
8880889888988898
"""
prog2="""
21234567000880
99999900000999
40330000000088
44988888888889
"""
def to_board(p):
	return [[*map(int,i)]for i in filter(None, p.split('\n'))]
 
print(f(to_board(prog)))
print(f(to_board(prog1)))
print(f(to_board(prog2)))

Zj1cCmxhbWJkYSBiOk0oc2V0KCksYiwwLDIsW10sKDAsMCkpClo9bWF4Clc9bWluCkw9ezA6WiwyOld9Cks9ezA6VywyOlp9ClQ9ezA6TCwxOkssMjpLLDM6TH0KUT17MDooMCwxKSwxOigxLDApLDI6KDAsLTEpLDM6KC0xLDApfQpJPXswOmxhbWJkYSBzLHYsKmE6WyphLFt2XStzXSwxOmxhbWJkYSBzLHYsKmE6WyphLHNbMTpdXSwyOmxhbWJkYSBzLHYsKmE6WyphLFtzdW0oc1s6Ml0pXStzWzI6XV0sMzpsYW1iZGEgcyx2LCphOlsqYSxbc1sxXS1zWzBdXStzWzI6XV0sNDpsYW1iZGEgcyx2LCphOlsqYSxbc1swXSpzWzFdXStzWzI6XV0sNTpsYW1iZGEgcyx2LCphOlsqYSxbc1sxXS9zWzBdXStzWzI6XV0sNjpsYW1iZGEgcyx2LHUscTpbW3UscSxzXSxbc1swXSt1JjMscSxzWzE6XV1dW1tdPHNdLDc6bGFtYmRhIHMsdix1LHE6W3Usc1swXSUyKjIsc1sxOl1dfQpkZWYgVihiLHgseSk6CiB0cnk6cmV0dXJuIGJbeF1beV0hPTlhbmQgeD4tMTx5CiBleGNlcHQ6cmV0dXJuIDAKZGVmIEMoYix2LHMpOgogcSxTLEQsZD1bc10sW3NdLHtzWzBdOltzWzFdXX0se3NbMV06W3NbMF1dfQogd2hpbGUgcToKICB4LHk9cS5wb3AoMCkKICBmb3IgbixtIGluIFEudmFsdWVzKCk6CiAgIHRyeToKICAgIGlmKFg6PXgrbik+LTE8KFk6PXkrbSlhbmR+LSgoWCxZKWluIFMpYW5kIGJbWF1bWV09PXY6cSs9KFgsWSksO1MrPShYLFkpLDtEW1hdPUQuZ2V0KFgsW10pK1tZXTtkW1ldPWQuZ2V0KFksW10pK1tYXQogICBleGNlcHQ6MQogcmV0dXJuIFMsRCxkCmRlZiBNKEgsYix1LHEscyxjLFA9MCxFPVtdKToKIGlmKF86PXN0cihbdSxxLHMsYyxQLEUsYltjWzBdXVtjWzFdXV0pKWluIEg6cmV0dXJuIHMKIEguYWRkKF8pO3gsKnk9QyhiLFM6PWJbY1swXV1bY1sxXV0sYykKIGlmIFA9PTg6cmV0dXJuIHMKIGlmIFMtODoKICBpZiB1IGluWzAsMl06WT1bWixXXVt1PjBdKHlbMV0pO1g9VFt1XVtxXSh5WzFdW1ldKQogIGVsc2U6WD1bWixXXVt1PT0zXSh5WzBdKTtZPVRbdV1bcV0oeVswXVtYXSkKIGVsc2U6WCxZPWMKIHJldHVybiBNKEgsYiwqKElbYltBXVtCXV0ocyxsZW4oeCksdSxxKWlmIGJbQV1bQl1pbiBJIGFuZChzIG9yIGJbQV1bQl08MillbHNlW3UscSxzXSksKEEsQiksMCxbXSlpZiBWKGIsQTo9WCtRW3VdWzBdLEI6PVkrUVt1XVsxXSllbHNlIFMtOGFuZCBNKEgsYixbdSwtfnUlNF1bUCUyXSxbMioocTwxKSxxXVtQJTJdLHMsKFgsWSksUCsxLFtdKW9yIE0oSCxiLC1+dSU0LDIqKHE8MSkscywoWCxZKSwwLEUrWyhYLFkpXSkKIApwcm9nID0iIiIKMTExMDkwOTA4MDA0CjkxMTA4ODgwODk0NAo5MTEwNjk5MTIzOTkKIiIiCnByb2cxPSIiIgoxMTk5OTk5OTk5OTk5OTk5Cjk4OTA4ODg4OTg4ODk4ODkKODg4MDg4ODAwMDg4ODgwOAo4ODgwODg5ODg4OTg4ODk4CiIiIgpwcm9nMj0iIiIKMjEyMzQ1NjcwMDA4ODAKOTk5OTk5MDAwMDA5OTkKNDAzMzAwMDAwMDAwODgKNDQ5ODg4ODg4ODg4ODkKIiIiCmRlZiB0b19ib2FyZChwKToKCXJldHVybiBbWyptYXAoaW50LGkpXWZvciBpIGluIGZpbHRlcihOb25lLCBwLnNwbGl0KCdcbicpKV0KCnByaW50KGYodG9fYm9hcmQocHJvZykpKQpwcmludChmKHRvX2JvYXJkKHByb2cxKSkpCnByaW50KGYodG9fYm9hcmQocHJvZzIpKSk=