当前位置：首页 > 洛谷 > 洛谷P3400题全1子矩阵计数算法解析：动态规划与栈优化解题实践

洛谷P3400题全1子矩阵计数算法解析：动态规划与栈优化解题实践

8个月前 (07-20)

一、题目解读

洛谷P3400题要求计算一个由0和1构成的二维矩阵中，所有全1子矩阵的数量。全1子矩阵指由连续1组成的矩形区域，无0元素。题目核心在于高效统计所有满足条件的子矩阵，需要兼顾时间复杂度和空间优化，属于经典动态规划与数据结构结合的算法题。

二、解题思路

采用“逐行扫描+栈优化”的策略。关键在于将二维问题转化为一维：每行视为独立高度数组，利用栈计算每个1元素的左右边界，进而通过边界差与高度乘积求得单行子矩阵数，最终累加各层结果。核心逻辑如下：

1. 预处理高度数组：逐行扫描，若当前为1，则继承上一行高度+1，形成柱状图结构。

2. 单行求解：利用栈维护递增高度序列，动态计算每个1元素的左右最远可达边界（即两侧首个更矮元素位置）。

3. 面积计算：子矩阵面积 = (右边界 - 左边界) × 高度 × 宽度（即当前高度），累加所有有效区域。

三、解题步骤

1. 预处理高度数组：通过嵌套循环读取输入，若字符为'1'，则h[i][j] = h[i-1][j] + 1，构建柱状图表示每列连续1的高度。

2. 逐行计算子矩阵数：

调用solveRow(row)函数：

a. 左边界计算：栈中维护递增高度，若新元素更矮，则弹出栈顶直至满足递增，当前左边界为栈顶元素位置。

b. 右边界同理反向遍历，确保边界严格最远。

c. 遍历每列，计算面积并累加。

3. 总结果累加：循环n行，累加每行子矩阵数，输出最终答案。

四、代码与注释

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAXN = 3005;
int h[MAXN][MAXN]; // 高度数组
int n, m;

// 计算单行中的全1子矩阵数
long long solveRow(int row) {
    stack<int> st;
    long long res = 0;
    vector<int> left(m+2), right(m+2);
    
    // 左边界计算
    for(int j = 1; j <= m; j++) {
        while(!st.empty() && h[row][st.top()] >= h[row][j]) {
            st.pop(); // 弹出更高元素，直至找到左边界
        }
        left[j] = st.empty()? 0 : st.top(); // 记录左边界位置
        st.push(j);
    }
    
    // 清空栈
    while(!st.empty()) st.pop();
    
    // 右边界计算（反向遍历）
    for(int j = m; j >= 1; j--) {
        while(!st.empty() && h[row][st.top()] > h[row][j]) {
            st.pop();
        }
        right[j] = st.empty()? m+1 : st.top();
        st.push(j);
    }
    
    // 计算结果
    for(int j = 1; j <= m; j++) {
        if(h[row][j] == 0) continue; // 跳过0元素
        res += (long long)(j - left[j]) * (right[j] - j) * h[row][j];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    long long ans = 0;
    
    // 预处理高度数组
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c; cin >> c;
            if(c == '1') h[i][j] = h[i-1][j] + 1; // 继承高度
            else h[i][j] = 0;
        }
    }
    
    // 逐行计算
    for(int i = 1; i <= n; i++) {
        ans += solveRow(i);
    }
    
    cout << ans << endl;
    return 0;
}