网格中不包含标记格子的矩形计数算法解析

1. 问题理解与建模这道题目要求我们计算在一个n×m的网格中所有不包含标记格子*的矩形的数量。这类问题在算法竞赛中非常典型属于二维平面上的矩形计数问题。1.1 问题重述给定一个n行m列的网格每个格子要么是.可用要么是不可用。我们需要计算所有由可用格子组成的矩形的数量。矩形的大小和形状没有限制只要不包含任何格子即可。1.2 问题转化这个问题可以转化为对于每个格子计算以它为右下角的所有合法矩形的数量。然后累加所有格子的这个数量就是总的合法矩形数。更高效的做法是对于每一行将其视为矩形的底边然后计算以该行为底边的所有合法矩形的数量。这种方法利用了单调栈来高效计算。2. 算法思路详解2.1 高度数组预处理首先我们需要预处理一个高度数组h[i][j]表示从位置(i,j)向上连续有多少个可用的格子即连续的.。这个预处理可以通过动态规划完成如果g[i][j] *则h[i][j] 0否则h[i][j] h[i-1][j] 1这样对于每一行i我们都有一个高度数组h[i][1..m]表示以该行为底边时每一列上的柱子高度。2.2 单调栈的应用对于每一行的高度数组h[i][1..m]我们需要计算以每个位置j为中心高度为h[i][j]的矩形能向左右扩展多远。这可以通过单调栈高效实现。具体来说对于每个位置j向左找到第一个小于h[i][j]的位置l向右找到第一个小于等于h[i][j]的位置r这样以h[i][j]为高度的矩形数量就是(j - l) × (r - j) × h[i][j]2.3 边界处理技巧为了简化代码实现我们通常在数组两端添加哨兵元素高度为0这样可以确保栈中所有元素都能被正确处理。3. 代码实现解析3.1 预处理高度数组for(int i1;in;i){ for(int j1;jm;j){ cing[i][j]; if(g[i][j].)h[i][j]h[i-1][j]1; else h[i][j]0; } }这段代码实现了高度数组的预处理。注意初始时h[0][j] 0这是边界条件。3.2 单调栈求左右边界void findl(int x){ p0; h[x][0]0; // 左哨兵 for(int im;i0;i--){ while(h[x][s[p]]h[x][i]p)l[s[p]]i,p--; s[p]i; } } void findr(int x){ p0; h[x][m1]0; // 右哨兵 for(int i1;im1;i){ while(h[x][s[p]]h[x][i]p)r[s[p]]i,p--; s[p]i; } }这两个函数分别计算每个位置的左右边界。注意findl是从右向左扫描找左侧第一个小于当前高度的位置findr是从左向右扫描找右侧第一个小于等于当前高度的位置使用严格大于和大于等于来避免重复计数3.3 计算结果long long work(int x){ findl(x); findr(x); long long res0; for(int i1;im;i){ res(i-l[i])*(r[i]-i)*h[x][i]; } return res; }这个函数计算以第x行为底边的所有合法矩形数量。对于每个位置i计算以h[x][i]为高度的矩形数量并累加。4. 算法复杂度分析预处理高度数组O(nm)每行的单调栈处理O(m)总共有n行所以总时间复杂度O(nm)空间复杂度O(m)单调栈的空间对于n,m≤1000的数据范围这个复杂度是完全可接受的。5. 关键点与注意事项5.1 为什么左侧用≤而右侧用这是为了避免重复计数。考虑相邻两个相同高度的柱子如果两侧都用≤会重复计算包含这两个柱子的矩形如果一侧用≤另一侧用可以确保每个矩形只被计算一次5.2 边界处理的重要性在单调栈的实现中添加哨兵元素h[x][0]和h[x][m1]设为0可以简化代码避免额外的边界检查。5.3 数据类型的选取由于结果可能很大最坏情况下约n²m²/4需要使用long long类型来存储结果避免溢出。6. 常见问题与调试技巧6.1 结果不正确可能原因高度数组预处理错误检查是否正确处理了*和.的情况单调栈实现错误检查比较符号和是否正确边界处理不当确保哨兵元素正确设置调试方法打印中间结果如高度数组、左右边界数组用小样例手动计算验证6.2 运行时间过长可能原因算法复杂度不是O(nm)检查是否有不必要的嵌套循环输入输出效率低使用快速IO如代码中的ios::sync_with_stdio优化建议确保使用快速IO避免不必要的内存操作7. 算法扩展与应用这种基于单调栈的矩形计数方法可以应用于许多类似问题最大全1子矩阵问题直方图中的最大矩形问题带权重的矩形计数问题理解这个算法的核心在于掌握如何将二维问题转化为一维问题高度数组单调栈如何高效计算边界如何组合这些信息得到最终结果8. 个人实现心得在实际编码中我发现以下几点特别重要清晰的变量命名如h表示高度l/r表示左右边界避免混淆统一的边界处理使用哨兵元素比在循环中检查边界更简洁模块化设计将findl和findr分开实现代码更清晰小样例测试手动计算小样例的结果验证代码正确性对于初学者建议先理解直方图最大矩形问题LeetCode 84这是本问题的一维版本理解后再扩展到二维会更容易。