[蓝桥杯]搭积木

搭积木

题目描述

小明对搭积木非常感兴趣。他的积木都是同样大小的正立方体。

在搭积木时，小明选取 mm 块积木作为地基，将他们在桌子上一字排开，中间不留空隙，并称其为第 0 层。

随后，小明可以在上面摆放第 1 层，第 2 层，......，最多摆放至第 nn 层。摆放积木必须遵循三条规则：

规则 1：每块积木必须紧挨着放置在某一块积木的正上方，与其下一层的积木对齐；

规则 2：同一层中的积木必须连续摆放，中间不能留有空隙；

规则 3：小明不喜欢的位置不能放置积木。

其中，小明不喜欢的位置都被标在了图纸上。图纸共有 nn 行，从下至上的每一行分别对应积木的第 1 层至第 nn 层。每一行都有 mm 个字符，字符可能是 '.' 或 'X' ，其中 'X' 表示这个位置是小明不喜欢的。

现在，小明想要知道，共有多少种放置积木的方案。他找到了参加蓝桥杯的你来帮他计算这个答案。

由于这个答案可能很大，你只需要回答这个答案对 109+7109+7 取模后的结果。

注意：地基上什么都不放，也算作是方案之一种。

输入描述

输入格式：

输入数据的第一行有两个正整数 n,m （n≤100，m≤100）n,m （n≤100，m≤100），表示图纸的大小。

随后 nn 行，每行有 mm 个字符，用来描述图纸。每个字符只可能是 '.' 或 'X' 。

输出描述

输出一个整数，表示答案对 109+7109+7 取模后的结果。

输入输出样例

示例

输入

2 3
..X
.X.

输出

4

运行限制

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

总通过次数: 296  |  总提交次数: 490  |  通过率: 60.4%

难度: 困难   标签: 2018, 国赛, 动态规划, 搜索

算法思路：动态规划 + 二维前缀和优化

本题需要计算在给定限制条件下搭建积木的方案数，核心是​​区间覆盖的动态规划​​，通过​​二维前缀和​​优化状态转移。以下是详细思路：

关键规则分析

1. ​​地基规则​​：地基（第0层）固定，方案数包含“什么都不放”的情况
2. ​​连续规则​​：每层积木必须连续且对齐
3. ​​禁止规则​​：'X'位置不能放置积木
4. ​​层级关系​​：第i层的积木必须完全包含在第i-1层的积木范围内

动态规划定义

• ​​状态设计​​：dp[i][l][r] 表示在第i层（图纸层）放置区间[l, r]积木的方案数（1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ m）
• ​​状态转移​​：dp[i][l][r] = Σ dp[i+1][x][y] 其中 x ≤ l, y ≥ r（第i+1层区间必须覆盖当前层）
• ​​前缀和优化​​：用二维前缀和sum[x][y]加速区间和计算

算法步骤

1. ​​初始化​​：
   • 第n层：合法区间方案数为1
   • 总方案数ans初始为1（什么都不放）
2. ​​自顶向下DP​​：
   • 从第n层向下到第1层
   • 计算第i+1层的前缀和
   • 根据覆盖规则计算第i层方案数
3. ​​累加方案​​：
   • 每层合法区间方案累加入ans
4. ​​输出结果​​：ans % 1e9+7

状态转移图解

第i+1层：覆盖区间[x,y]|-----------| ← y|   [l,r]   |x→ |-----------|↑必须满足：x ≤ l 且 y ≥ r第i层：区间[l,r]（需被完全覆盖）

代码实现（C++）

#include <iostream>
#include <vector>
using namespace std;const int mod = 1000000007;int main() {int n, m;cin >> n >> m;vector<string> grid(n);for (int i = 0; i < n; i++) {cin >> grid[i];}// dp[i][l][r]: 第i层放置区间[l,r]的方案数vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(m + 1, 0)));long long ans = 1;  // 包含"什么都不放"的情况// 初始化第n层for (int l = 1; l <= m; l++) {for (int r = l; r <= m; r++) {bool valid = true;for (int j = l - 1; j <= r - 1; j++) {if (grid[n - 1][j] == 'X') {valid = false;break;}}if (valid) {dp[n][l][r] = 1;ans = (ans + 1) % mod;}}}// 自顶向下DP（从n-1层到1层）for (int i = n - 1; i >= 1; i--) {// 计算第i+1层的前缀和vector<vector<int>> sum(m + 1, vector<int>(m + 1, 0));for (int x = 1; x <= m; x++) {for (int y = 1; y <= m; y++) {long long val = dp[i + 1][x][y];val = (val + sum[x - 1][y]) % mod;val = (val + sum[x][y - 1]) % mod;val = (val - sum[x - 1][y - 1] + mod) % mod;sum[x][y] = val;}}// 计算第i层DP值for (int l = 1; l <= m; l++) {for (int r = l; r <= m; r++) {// 检查禁止位置bool valid = true;for (int j = l - 1; j <= r - 1; j++) {if (grid[i - 1][j] == 'X') {valid = false;break;}}if (!valid) {dp[i][l][r] = 0;continue;}// 状态转移：Σ(x≤l, y≥r) dp[i+1][x][y]long long temp = sum[l][m];        // x≤l, y≤mtemp = (temp - sum[l][r - 1] + mod) % mod;  // 减去y<r的部分dp[i][l][r] = temp;ans = (ans + temp) % mod;}}}cout << ans << endl;return 0;
}

实例验证（输入样例）

输入：2 3..X.X.
输出：4

计算过程：

1. ​​第2层（顶层）​​：
   • [1,1]：合法 → dp[2][1][1]=1
   • [3,3]：合法 → dp[2][3][3]=1
   • 其他区间非法 → 方案数0
   • 累计：ans=1+2=3
2. ​​第1层​​：
   • [1,1]：合法，覆盖dp[2][1][1] → 方案数1
   • 其他区间非法 → 方案数0
   • 累计：ans=3+1=4

注意事项

1. ​​下标处理​​：
   • 图纸行索引：grid[i-1]对应第i层
   • 字符索引：区间[l, r]对应字符串[l-1, r-1]
2. ​​负数取模​​：
   • 减法后加mod再取模，避免负数
3. ​​空间优化​​：
   • 三维数组大小：(n+1)×(m+1)×(m+1)
   • 最大空间：101×101×101×4B ≈ 4MB
4. ​​时间优化​​：
   • 二维前缀和将转移复杂度从O(m⁴)降至O(m²)
   • 总复杂度：O(n×m²)

优化建议

1. ​​滚动数组​​：用dp[2][m][m]替代三维数组
2. ​​区间压缩​​：连续'.'区间合并减少状态数
3. ​​剪枝策略​​：
   • 提前终止全'X'层的计算
   • 跳过无效区间（l>r）