Yes, it's correct.

We got WA but passed with some additional random strategy. Not sure whether our first solution has some bugs.

abistrigova used backtracking with memoization and restriction on iterations.

If we don't know the two ends?

Brute force from both borders to middle, with checking s for which all is known works in $$$O(2^{3n/4})$$$, because one ? in first two lines can be found because of modulo 4 equation, and one in last two lines can be found.

In fact, you don't need to find them, this only proves, that for each s, at least 1/4 of branches will be thrown away imidiatly.

The same proved complexity but probably faster in practice (and works in 5 ms): Do a recursive brute in this order: first and last column first, then going inside, and checking that currently everything is ok.

What's MITM?

You can find with DP in $$$O(n \cdot 2^n)$$$ that the answer is a linear recurrence of order $$$8$$$. So you can solve it with Berlekamp-Massey.

Let $$$f[S]$$$ be the possibility that you start from $$$0$$$ to state $$$S$$$, where $$$S$$$ is a $$$n$$$-bit integer. The state means you are now at $$$0$$$ and a position $$$k$$$ is visited if and only if $$$S_k=1$$$.

For each state $$$S$$$, find the first and last $$$11$$$, and set all the bits between them to $$$1$$$.

i.e.

0010101011000110000110101 -> 0010101011111111111110101

It is not hard to prove that the number of states is now acceptable.

Solution from my team: run random simulation multiple times, print arithmetic mean of number of moves in all simulations.