1. O(m^2 n^2) subproblems.

There are "m+1 choose 2" = (m+1)m/2 = O(m^2) possible choices of r,s,
and "n+1 choose 2" = (n+1)n/2 = O(n^2) possible choices of t,u.  They
can be combined independently, so we have a total of O(m^2) * O(n^2)
= O(m^2 n^2) subproblems.

2. mn subproblems.

There are m choices for x, and n choices for y, so mn subproblems.
O(mn) is also a fine answer.


Comments:

Professor Celadon's approach leads to a O(m^2 n^2) algorithm,
e.g., using the recursive definition
  F(r,s,t,u) = F(r,s,t,u-1) AND F(r,s,u,u)      if t < u
along with some base cases for the case where t=u.

Professor Ecru's approach leads to a O(mn) algorithm, e.g., using
the recursive definition
  E(x,y) = "0x0"    if M[x][y] != 0
  E(x,y) = the largest of E(x-1,y) + 1 row  and  E(x,y-1) + 1 column
                if M[x][y] = 0
along with some base cases.