Continuity

This is an exceptionally difficult Dynamic Programming problem. Brute force works well enough for $N \leq 5$ , but immediately becomes intractable afterwards. What's worse, searching on OEIS only gives the answer up to $N = 7$ , and links to no papers or formulas! How do you count continuous grids?

One such solution is to go column by column, multiplying results. Consider, for example, the graph below:

Imgur

Suppose we only know the number of ways there are to fill the blue squares, such that the middle column appears as it is. We only need that knowledge of the middle column's appearance, in this case, to compute how many ways there are to fill the green squares - then, we can just multiply that result by the number of ways there are to fill the blue squares.

This works in any case where the middle column is just one continuous segment of black squares. If we face a situation like the one below, we need more information:

Imgur

We need to know how the segments are connected, if at all, as that will govern how we can fill out the rest of the grid. It turns out this information, the connectivity of the segments, is really easy to normalize: Consider all the connected components in the blue squares, and list them in order of height (that is, the highest y-coordinate in the middle column that they touch). Using that order, assign an identifier to each connected component, and then simply label each segment in the middle column by that identifier.

This connectivity information is all we need to keep advancing. We can consider, for any possible 'middle' column, the set of all $2^N$ possible 'next' columns, and for each one, compute the new connectivity state. There are, approximately, $2^{1.5N}$ connectivity states, (identifiers + middle-column state), so it would take about $2^{2.5N}$ operations to compute the number of ways there are to transition to any connectivity state, from any prior connectivity state. For $N = 10$ , this is on the order of $2^{25}$ , which is doable.

The empty case - when the middle column is empty - is a little ugly. We could add another bit to our connectivity state, to keep track of whether we've "already built" the blob or not. Or, we could add a little bit of complexity to our counting routine at the end instead.

Let $C$ be the set of all possible connectivity states. Let $M_{C,C}$ be the matrix, which defines the number of ways there are to transition from any connectivity state $c_1$ to $c_2$ , storing $0$ if there are none. We can compute the total number of continuous $N \times N$ grids in the following pseudo-code manner:

# We don't let the empty state count here
map<C, num> init = {possible_first_C_states} -> 1 # 2^N - 1
sum = sumValidEndingCStates(init) * N
map<C, num> last_map = init
for i in 2..N:
  map<C, num> next_map = new map(default = 0)
  for c1 in last_map.keys:
    for c2 in M.row(c1):
      next_map[c2] += last_map[c1] * M.val(c1, c2)
  sum += sumValidEndingCStates(next_map) * (N + 1 - i)
  last_map = next_map

print sum

The 'sumValidEndingCStates' routine merely sums the values in the given map, for where the keys yield only one identifier in the connectivity state. (Meaning that we could stop adding columns then, and what we've built so far would be fully connected).

The full algorithm runs in time $O(2^{2.5N} + N \cdot \left| M_{C,C} \right| )$ . It turns out that $M_{C,C}$ is, predictably, a relatively sparse matrix, with much fewer than $2^{2.5N}$ elements, and so the major runtime of the algorithm is approximately $O(2^{2.5N})$ .

The above routine can be examined in the main method of the source code . It can be verified that the output of the code does in fact match the OEIS sequence up through $N = 7$ , as well.

---

And running it with $N = 10$ yields the enormous result:

$\boxed{284374318545830329487309785}$