额。。我有罪，WA了5次

仰慕2楼

需要数组吗？

先设一个f[i]表示恰好走i步且不经过已走的点 共有的走法。
如果向上走，不会出现经过已走的点；如果向左或右，上一步不能是向右或左。
这一步的选择数= (3*上一步的所有选择中向上走的选择数) + (2*上一步的所有选择中向左、右走的选择数)。
上一步的所有选择中向上走的选择数”实际上就是“上上步的所有选择数”即f[i-2]
“上一步的所有选择中向左、右走的选择数” 等于 “上步所有的选择数(即f[i-1])-上步向上的选择数”
也就等于 “上步所有的选择数(即f[i-1])-上上步所有的选择数(即f[i-2])”
所以得到递推式：f[i] = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);

滚动数组无限好用啊
（Ps:加减乘直接 % 或 mod 12345）