[蓝桥杯]格子刷油漆

格子刷油漆

题目描述

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

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

比如：a d b c e f 就是合格的刷漆顺序。c e f d a b 是另一种合适的方案。

当已知 NN 时，求总的方案数。当 NN 较大时，结果会迅速增大，请把结果对 109+7109+7 取模。

输入描述

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

输出描述

输出数据为一个正整数。

输入输出样例

示例

输入

2

输出

24

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 448  |  总提交次数: 645  |  通过率: 69.5%

难度: 中等   标签: 2013, 国赛, 动态规划

格子刷油漆问题：动态规划解法

问题分析

在 2×N 的网格上刷油漆，规则如下：

• 从任意格子开始，每次移动到相邻格子（包括对角相邻）
• 不能跳过未刷的格子
• 最终方案数需对 109+7 取模

这是一个典型的动态规划问题，需要定义两个核心数组：

• ​​a[i]​​：从左上角出发，刷完 2×i 网格后停在任意位置的方案数
• ​​b[i]​​：从左上角出发，刷完 2×i 网格后回到同列下方格子的方案数

动态规划递推公式

1. ​​初始化边界条件​​：

   • b[1]=1（单列网格只有 1 种回路方案）
   • a[1]=1（单列网格只有 1 种遍历方案）
   • a[2]=6（2×2 网格有 6 种遍历方案）

2. ​​状态转移方程​​：

   • ​​回路方案​​：b[i]=2×b[i−1]mod109+7
     （每增加一列，回路方案翻倍）
   • ​​遍历方案​​：a[i]=(2×a[i−1]+b[i]+4×a[i−2])mod109+7
     （含三种情况：向下刷、向右刷、折返刷）

3. ​​总方案计算​​：

   • ​​四个角出发​​：4×a[n]
   • ​​中间列出发​​（第 2 至 n−1 列）：
   • 
   • （每个中间列有 2 个起点，左右双向遍历各需回路和自由路径组合）

     #include <iostream>
     #include <vector>
     using namespace std;const int MOD = 1000000007;
     const int MAX_N = 1000;int main() {int n;cin >> n;// 特殊处理 n=1if (n == 1) {cout << 2 << endl;  // 两个起点各1种方案return 0;}vector<long long> a(MAX_N + 1, 0);vector<long long> b(MAX_N + 1, 0);// 初始化基础状态b[1] = 1;for (int i = 2; i <= n; i++) {b[i] = (2 * b[i - 1]) % MOD;  // 回路方案递推}a[1] = 1;a[2] = 6;for (int i = 3; i <= n; i++) {// 三种情况：向下刷、向右刷、折返刷a[i] = (2 * a[i - 1] + b[i] + 4 * a[i - 2]) % MOD;}// 计算总方案：四个角 + 中间列long long total = 4 * a[n] % MOD;for (int i = 2; i < n; i++) {long long term1 = (8 * b[i - 1] % MOD) * a[n - i] % MOD;long long term2 = (8 * b[n - i] % MOD) * a[i - 1] % MOD;total = (total + term1 + term2) % MOD;}cout << total << endl;return 0;
     }

     关键测试点验证

     输入 N	输出	说明
     1	2	两个起点各1种方案
     2	24	4个角方案 + 中间方案
     3	96	递推组合验证
     22	359635897	大数取模验证

     复杂度分析

   • ​​时间复杂度​​：O(N)，单次遍历递推
   • ​​空间复杂度​​：O(N)，存储状态数组
   • ​​适用场景​​：N≤1000，满足题目约束（1秒时限）