I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no cell of another region is in either of the designated directions from a cell of a given region, e. g. no cell from a different region is either above or to the left of a cell in the top left region.
I can see that a region will either be rectangular (possibly degenerate) or will share a (possibly irregular) stairstep-shaped border with the opposite region, in which case the other two regions will necessarily be rectangular. I thus thought to count the number of stairstep paths between (possibly identical) points on an $(n+1) \times (n+1)$ lattice, which I know would be $$2\left(\sum _{k=1}^n\sum_{r=1}^n {{k+r} \choose k} + (n + 1){{n+1} \choose 2}\right)+(n+1)^2$$ which, when simplified is$$n^3+3n^2-n-3+2{{2n+2}\choose {n+1}}$$
This needs to be adjusted for overcounting (and undercounting), though: divisions with all rectangular regions where one or more are degenerate have a many-to-many correspondence with paths, but I'm having a bit of trouble with the exact corrections to make.
I'm actually trying to compute this as part of a larger calculation, so I'd like to find ways to improve the time-complexity of the algorithm. In this particular case, for $n>2$, when I'm trying to calculate $D_n$, I'll already know $D_a$ and $D_b$ for some $(a,b)$ where $a+b=n$ so a recurrence relation would be nice.
This is a project Euler problem (or rather isomorphic to one), so I'm looking more for hints/suggestions etc. than actual answers, but any help is appreciated.
Note: in case it wasn't clear, for the purposes of this question, a stairstep path from point $a$ to point $b$ along the lattice in which the distance to point $b$ is strictly decreasing. Paths go both ways, so the path from $a$ to $b$ is equivalent to the reverse path from $b$ to $a$.
update: joriki pointed out that this is the same problem as Number of Ways to Fill a Matrix with symbols subject to Weird contsraint.. That question's page has a closed form, but no derivation. I am still interested in computing it quickly for large n, though it's worth noting that the answers in this particular case are taken modulo a large number (which I suspect is probably prime), if that changes anything.