用 a[i] 表示把 i 个格子按要求涂色的涂法，易得：
当 i=1 时，有 1 个格子时有 3 种涂法；当 i=2 时，有 2 个格子时有 6 种涂法；当 i=3 时，有 3 个格子时有 6 种涂法。
当 i≥4 时，假设已经求出 a[1]~a[i−1]，求 a[i]，对于 a[i−1] 有两种情况：
（1）第 i−1 格的涂色合法，即在没有加入第 i 个格子的时候，第 i−1 个格子和第 i−2 个格子颜色不同且和第 1 个格子的颜色也不相同。当加入第 i 个格子，第 i 个格子的颜色已经是确定的。所以此时的方案数为：
a[i−1]×1=a[i−1]
（2）第 i−1 格的涂色不合法(对于整体的 i 个格子依然是合法的)，即在没有加入第 i 个格子的时候，即第 i−1 个格子和第 i−2 个格子颜色不同但是和第 1 个格子的颜色相同。当加入第 i 个格子，第 i 个格子有两种情况。此时的方案数为：
a[i−2]×1×2=2×a[i−2]
分类用加法原理，分步用乘法原理
综合以上两种情况：
a[i]=a[i−1]+2×a[i−2]，i≥4
1、定义变量n,进行输入,定义数组a,进行存储
2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法
3、递推式:a[i]=a[i-1]+2*a[i-2]
4、输出
