Bulgaria

Denote by $c_n$ the number of the sequences from the problem. Define the number $d_n$ in a similar way but replacing the given equality by $$x_{A_i}-x_{A_{i-1}}+|y_{A_i}-y_{A_{i-1}}|=1,1\le i\le n;$$ call the respective sequences right and the other sequences wrong. It is not difficult to see that $d_0=1$, $d_1=2$ and $d_{i+2}=d_{i+1}+d_i$ (to any right sequence $A_0,A_1,\dots ,A_{i+2}$ associate $A_0,A_1,\dots ,A_{i+1}$ if $x_{A_{i+2}}=x_{A_{i+1}}$, and $A_0,A_1,\dots ,A_i$ otherwise). It follows that $d_n$ is $(n+2)$-th Fibonacci number $f_{n+2}$. We associate to any wrong sequence $A_0,A_1,\dots ,A_n$ ($n\ge 3$) the right sequence $A_0,A_1,\dots ,A_k$ for which $x_k=x_n$, $k\le n-3$. It is clear that $x_{k+1}=x_k+1$; we shall call such sequences super right. Note that the number of the super right sequences of length $k$ is equal to $$(2)d_{k-1}=f_{k+1}$$ (this remains true for $k=0$). There is an obvious bijection between the set of the wrong sequences of length $n$ and the set of the super right sequences with lengths $n-3,n-5,\dots$. It follows by (2) and (1) that $$c_n=d_n+d_{n-1}+d_{n-2}+\cdots =2f_{n+1}-{\epsilon }_n=\frac{2}{\sqrt{5}}(q^{n+1}-(1-q{)}^{n+1})-{\epsilon }_n,$$ $$\text{where }{\epsilon }_n=\frac{1+(-1{)}^n}{2}\text{ and }q=\frac{1+\sqrt{5}}{2}.$$