C++ 单调栈统计无障碍矩形数量（P3345）

好的，我们先把问题分析透彻，然后给出一个高效的C++解决方案。这道题是一道经典的**动态规划 + 单调栈**的问题，目标是在有障碍物的网格中，数出所有不包含障碍物的矩形个数。 --- ## 🧩 问题理解 我们有一个 `n x m` 的网格，每个格子可能是： - `*` 表示障碍（不能剪到） - `.` 表示空白（可以剪） 我们需要统计所有**子矩形**的数量，要求子矩形内部没有 `*`。 ### · 举例说明 例如样例： ``` .... .*** .*.. .*** ...* .*** ``` 有38个合法矩形。 --- ## 🧠 思路分析 ### 🔹 暴力做法 最直接的是枚举所有子矩形的左上角 `(i, j)` 和右下角 `(k, l)`，检查是否全是 `.`。 - 复杂度：`O(n^2 * m^2)` - 对于 `n, m <= 1000` 完全不可行。 ### 🔹 优化思路——逐行处理 我们可以**按行处理**，将问题转化为： - 在第 `i` 行及之前，对于每一列 `j`，记录从当前行向上连续空白格的数量，记作 `height[j]`。 - 这样的 `height` 数组实际上表示的是以当前行为底边的直方图的高度。 - 这时，我们需要统计**以当前行为底边**的、内部全部为空的矩形数量。 问题转化为：**给定一个直方图，求其中所有不包含0高度的子矩形数量**（注意这里的“直方图高度”只由连续空白格构成，且矩形必须与该直方图高度对齐）。 ### 🔹 关键技巧——单调栈 对于每一行： 1. 维护一个 **单调递增栈**，存储 `(高度, 该高度可扩展的最左位置)`。 2. 对于每个高度 `h`： - 以当前高度作为矩形高度时，它可以向左扩展到的位置是由栈中前一个比它低的高度的索引 + 1决定。 - 以当前高度为高、以某个宽度 `w` 为宽的矩形数量 = `h * w`？不，这里我们的矩形高度是确定的 `h`，但每个合法的高度扩展取决于我们取哪一个高度作为顶边。 更准确的做法是： 在求以某列为右边界的矩形数量时，使用一个技巧： - 设 `h[j]` 为当前列的高度。 - 对每个位置 `j`，我们通过单调栈找到左边第一个高度小于 `h[j]` 的位置 `L`。 - 对于 `L+1` 到 `j` 之间的列，如果把当前行作为底边，矩形的高度可以是这些列中最低的高度，但最小高度不低于 `h[j]` 的那些连续列，能贡献多少种宽度的矩形？ 更通用的方法： - 我们以 `height[j]` 为底，对每个高度 `h`，统计以这个高度为矩形高度的数量。栈中每弹出一个高度，同时就可以通过其宽度计算该高度能构成的矩形数。 **公式**： 当我们弹出高度 `h` 时，设其左边界为 `left`，当前索引为 i，那么宽度 `w = i - left`，以高度 `h` 为高的矩形数量就是 `h * (w*(w+1)/2)` 吗？——不是的，这里是所有以 `h` 为**矩形高度**的矩形数量：对于这个宽度段（连续且高度至少为 h），我们可以选择1~w的宽度，每个宽度都能形成以当前高度为高度的矩形，所以数量是： ``` h * (w * (w+1) / 2) ``` 因为每种宽度对应 `h` 种上边界选择（从当前高度往下数h种高度起点的矩形）。 ### 🔹 另一种易理解的做法（逐列扩展高度） 另一种做法是： 对于每一列，维护它向上可以到达的最大安全高度。 然后用这组高度数组，每行每行压入单调栈计算。 注意我们的数据量是1000×1000，O(n*m) 是可行的。 --- ## 💻 最终代码实现 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<char>> grid(n, vector<char>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> grid[i][j]; } } vector<int> height(m, 0); long long total = 0; for (int i = 0; i < n; ++i) { // 更新高度 for (int j = 0; j < m; ++j) { if (grid[i][j] == '.') { ++height[j]; } else { height[j] = 0; } } // 单调栈，计算以当前行为底边的所有矩形数量 stack<int> st; // 增加一个高度为0的哨兵，便于统一处理栈内剩余元素 vector<int> h = height; h.push_back(0); for (int j = 0; j <= m; ++j) { while (!st.empty() && h[st.top()] > h[j]) { int idx = st.top(); st.pop(); int left = st.empty() ? -1 : st.top(); int width = j - left - 1; // 以 h[idx] 为高的矩形，高度选择有h[idx]种 // 宽度能选1..width，所以宽度方案数 = width*(width+1)/2 total += (long long)h[idx] * (width * (width + 1LL) / 2); } st.push(j); } } cout << total << "\n"; return 0; } ``` --- ## ⚙️ 复杂度分析 - 时间复杂度：**O(n * m)** - 外层循环 n 次，内层循环 m 次，加上单调栈操作平摊 O(1) 每次。 - 空间复杂度：**O(m)**（高度数组 + 栈） --- ## ⚠️ 易错点与开发建议 1. **整数溢出**：n,m <= 1000，最坏情况下矩形数量可达到 (n*(n+1)/2)*(m*(m+1)/2) ≈ 2.5e11，因此必须使用 `long long` 计数。 2. **哨兵技巧**：在最后插入一个高度为0的柱子，可以保证栈中所有高度最终都会弹出，避免遗漏。 3. **连续空白段**：单调栈每次弹出的宽度计算需小心索引左边界，`left` 是栈中前一个元素的位置（或-1），`j` 是当前右边界。 4. **调试建议**：可以先用小规模数据暴力验证正确性。 --- ## 🚀 扩展与延伸 - 如果题目改成统计**正方形**的数量，只需将 `width*(width+1)/2` 改为 `min(h[idx], width)` 的累加。 - 类似问题可以用于：最大全1子矩阵面积、最大全1子矩阵数量等，都是经典的单调栈应用。 - 如果 `n,m` 更大（例如 2000），仍然可以使用 O(n*m) 方法，可考虑使用数组模拟栈以加速。 --- ######[AI写代码神器 | 1687点数解答 | 2026-06-14 19:52:20]