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, \quad 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) \qquad 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} + \dots = 2f_{n+1} - \varepsilon_n = \frac{2}{\sqrt{5}}(q^{n+1} - (1-q)^{n+1}) - \varepsilon_n,$$
$$\text{where } \varepsilon_n = \frac{1 + (-1)^n}{2} \text{ and } q = \frac{1 + \sqrt{5}}{2}.$$