[蓝桥杯][2013年第四届真题]格子刷油漆_蓝桥杯2013年第四届真题-格子刷油漆-CSDN博客

　　题目描述

　　X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。

　　你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）

　　比如：a d b c e f 就是合格的刷漆顺序。

　　c e f d a b 是另一种合适的方案。

　　当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。 输入

　　输入数据为一个正整数（不大于1000） 输出

　　输出数据为一个正整数。 输入样例

　　3 输出样例

　　96 思路

　　首先这个题目我们可以从它走的路线的情况方面考虑，定义数组a和数组b,数组a存放的是从起点出发，一趟不回来的情况，数组b存放的是从起点出发，还能回来的情况；

　　起点可以从4个顶点和中间的点开始考虑

　　1.从顶点出发：

　　第一种情况：第一步走同一列的另外一个格子，再走下一列，重复操作，一直走下去，属于不回来的情况，可以画个图，可知a[i]=2*a[i-1],2指的是i-1列走到i列有两种选择情况

　　第二种情况：第一步走下一列，第二步还是走下一列，走到最后再返回，由于行固定为2，所以回来的路径是唯一的，可知b[i] = 2 * b[i-1]

　　第三种情况：第一步走另一列，第二步由该列再走回来，第三步走另外一列剩余的格子，可知a[i] = 2 * 2 * a[i-2];

　　2.从中间出发

　　有两种，先从中间第i列往左边出发，再回到右边，可知方案数b[ i ] × ( 2 × a[ n-i ]），从中间第i列往右边出发，再回到左边的方案数(b[ n-i+1]) × (2×a[ i - 1])

　　最后可以得出总的方案数：4×a[n] + 2×2×( b[ i ]×a[ n-i ] + b[ n-i+1 ]×a[ i - 1] )