All-one Matrices - 题解

标签与难度

标签: 动态规划, 矩阵, 二维DP, 矩形计数, 数据结构难度: 2000

题目大意喵~

你好呀，亲爱的小伙伴！Gromah 和 LZR 在一座神秘的古墓里发现了一个挑战，喵~ 他们面对一个 $n \times m$ 的大矩阵，里面只有 '0' 和 '1' 两种数字。

旁边的小纸条上写着任务：需要我们找出所有“全 1 子矩阵”中，那些没有被任何其他更大的“全 1 子矩阵”完全包含的矩阵，并数出它们的数量。这个数量就是打开下一关密码锁的密码哦！

简单来说，我们要找的就是所有“极大”的全 1 子矩阵。比如说，如果一个 2x2 的全 1 矩阵旁边还有一个 2x1 的全 1 区域，它们共同组成了一个 2x3 的全 1 矩阵，那么我们只应该计数这个大的 2x3 矩阵，而不是那个小的 2x2 矩阵，因为它被更大的矩阵“吞掉”啦，喵~

解题思路分析

这道题真是个有趣的挑战呢，喵！暴力枚举所有子矩阵的左上角和右下角，再检查里面是不是全是 '1'，那复杂度可是 $O(n^3 m^3)$ 级别的，肯定会超时的说。所以，我们得想个更聪明的办法，呐。

这种在网格里找特定形状的问题，通常都可以用动态规划（DP）来解决哦！让我带你一步步拆解这个问题吧！

第一步：从二维到一维的思考转换

直接思考二维的极大矩形有点复杂，我们可以换个角度。对于矩阵中的每一个 '1'，我们都可以把它想象成一个矩形的底边的一部分。

如果我们能算出，对于每个是 '1' 的格子 (i, j)，以它所在行为底边、向上延伸所能构成的最大全 1 矩形是多大，问题是不是就清晰多啦？

为了描述这样一个矩形，我们需要三个关键信息：

高度 (Height): 从 (i, j) 向上连续的 '1' 有多少个。
左边界 (Left Boundary): 这个矩形最远能延伸到哪一列。
右边界 (Right Boundary): 这个矩形最远能延伸到哪一列。

第二步：动态规划计算矩形信息

我们可以用三个二维数组 h[i][j], l[i][j], r[i][j] 来分别存储以 (i, j) 为右下角（或者说，底边包含 (i, j)）的矩形的高度、左边界和右边界。

1. 计算高度 h[i][j] 这个最简单啦！如果 grid[i][j] 是 '1'，它的高度就是它上面那个格子 (i-1, j) 的高度加一。如果 grid[i][j] 是 '0'，那高度就是 0。

h[i][j] = (\text{grid}[i][j] == '1') ? (h[i-1][j] + 1) : 0

2. 计算左右边界 l[i][j] 和 r[i][j] 这部分稍微有点小技巧哦！一个矩形不仅要在当前行 i 是连续的 '1'，在它上面的每一行（直到高度 h[i][j] 的限制）也必须是连续的 '1'。这意味着，在第 i 行的左右边界，必须同时满足第 i-1 行的边界限制。

我们可以分两步计算：

首先，我们只考虑当前行 i。计算出一个临时的左边界 cur_l[j] 和右边界 cur_r[j]。cur_l[j] 是第 i 行中包含 (i, j) 的连续 '1' 段的起始列，cur_r[j] 是结束列。这可以通过两次简单的行内遍历完成。
然后，我们将当前行的限制和上一行的限制结合起来。以 (i, j) 为底的矩形，它的左边界不能比 (i-1, j) 对应的矩形的左边界更小，也不能比当前行 i 的 cur_l[j] 更小。所以，真正的左边界是两者的最大值。右边界同理，是两者的最小值。
- l[i][j] = max(l[i-1][j], cur_l[j])
- r[i][j] = min(r[i-1][j], cur_r[j])

如果格子 (i-1, j) 是 '0'，那么矩形就是从第 i 行重新开始的，l[i][j] 和 r[i][j] 就直接等于 cur_l[j] 和 cur_r[j]。

通过这个DP过程，我们对于每一个 '1' 格子 (i, j)，都求出了以它为底边一部分的最大矩形。这个矩形的四条边分别是：

上: i - h[i][j] + 1
下: i
左: l[i][j]
右: r[i][j]

第三步：筛选出“极大”的矩形

现在我们有一大堆矩形了，但很多都是重复的，或者被其他更大的矩形所包含。怎么找出那些“极大”的呢？

一个矩形是极大的，意味着它不能再向上下左右任何一个方向扩展。

向上、向左、向右：我们的DP计算方式已经保证了这一点。h[i][j] 的定义保证了 (i - h[i][j], j) 这一行是 '0'（或者出界），l[i][j] 和 r[i][j] 的定义也保证了无法再向左右扩展。
向下：这是我们唯一需要检查的方向！

一个以第 i 行为底的矩形 Rect_A，如果能向下扩展，就意味着它被一个以第 i+1 行为底的矩形 Rect_B 完全包含了。

所以，我们的筛选条件是：对于由 (i, j) 定义的矩形，如果它下面的格子 (i+1, j) 是 '0'，或者整个矩阵就在第 i 行结束了，那么它肯定不能向下扩展，它就是极大的！如果 (i+1, j) 是 '1'，我们就比较一下 (i, j) 定义的矩形和 (i+1, j) 定义的矩形。如果 (i+1, j) 定义的矩形的左右边界完全“覆盖”了 (i, j) 的矩形的左右边界（即 l[i+1][j] <= l[i][j] 并且 r[i+1][j] >= r[i][j]），那么 (i, j) 的矩形就被包含了，不是极大的。反之，它就是极大的。

第四步：去重计数

我们遍历所有格子 (i, j)，判断由它定义的矩形是否是极大的。如果是，我们就找到了一个候选者。

但是要注意，一个极大的矩形可能会被它底边的多个格子 (i, j) 同时发现。比如一个 2x3 的矩形，它底边的 3 个格子都会把它找出来一次。为了不重复计数，我们可以把找到的极大矩形的四个坐标 (top, left, bottom, right) 存入一个 std::set 中。set 会自动帮我们处理重复的情况，喵~

最后，set 的大小就是我们要求的答案啦！

总结一下流程：

DP计算出所有格子的 h, l, r 值。
遍历所有格子 (i, j)。
如果 grid[i][j] 是 '1'，检查由它定义的矩形是否满足“向下极大”的条件。
如果满足，将该矩形的四元组坐标 (top, left, bottom, right) 加入 set。
最终答案就是 set 的大小。

代码实现

这是我根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <tuple>

// 使用 using namespace std 可以让代码更简洁，但在大项目中要小心命名冲突哦
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    // 使用 vector<string> 来读取和存储矩阵，非常方便喵~
    // 我们在周围加了一圈padding，处理边界情况时就不用写那么多 if-else 啦
    vector<string> grid(n + 2, string(m + 2, '0'));
    for (int i = 1; i <= n; ++i) {
        cin >> grid[i];
        grid[i] = "0" + grid[i] + "0"; // 在每行左右也加上 padding
    }

    // DP 数组，h是高度，l是左边界，r是右边界
    vector<vector<int>> h(n + 2, vector<int>(m + 2, 0));
    vector<vector<int>> l(n + 2, vector<int>(m + 2, 0));
    vector<vector<int>> r(n + 2, vector<int>(m + 2, 0));

    // --- 动态规划计算 h, l, r ---
    for (int i = 1; i <= n; ++i) {
        // 1. 计算当前行 i 的临时左右边界 (只看水平方向)
        vector<int> cur_l(m + 2, 0);
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '1') {
                cur_l[j] = (grid[i][j - 1] == '1') ? cur_l[j - 1] : j;
            }
        }
        vector<int> cur_r(m + 2, 0);
        for (int j = m; j >= 1; --j) {
            if (grid[i][j] == '1') {
                cur_r[j] = (grid[i][j + 1] == '1') ? cur_r[j + 1] : j;
            }
        }

        // 2. 结合上一行的信息，更新最终的 h, l, r
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '1') {
                h[i][j] = h[i - 1][j] + 1;
                // 如果能从上面继承，边界就是当前行和上一行边界的交集
                // 左边界取大的，右边界取小的，就像取区间的交集一样
                if (grid[i - 1][j] == '1') {
                    l[i][j] = max(l[i - 1][j], cur_l[j]);
                    r[i][j] = min(r[i - 1][j], cur_r[j]);
                } else { // 如果不能继承，就从当前行开始
                    l[i][j] = cur_l[j];
                    r[i][j] = cur_r[j];
                }
            }
        }
    }

    // --- 筛选并用 set 去重 ---
    // tuple 可以把多个值打包在一起，作为 set 的元素，很方便！
    set<tuple<int, int, int, int>> maximal_rects;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '0') {
                continue;
            }

            // 判断以 (i, j) 为底的矩形是否是极大的
            // 极大 <=> 不能被 (i+1, j) 的矩形所包含
            bool is_maximal = false;
            if (grid[i + 1][j] == '0') {
                // 下面是0，无法延伸，是极大的
                is_maximal = true;
            } else {
                // 下面是1，检查是否被下方的矩形包含
                // 如果下方的矩形没有完全覆盖当前矩形的宽度，那当前矩形就是极大的
                if (l[i + 1][j] > l[i][j] || r[i + 1][j] < r[i][j]) {
                    is_maximal = true;
                }
            }

            if (is_maximal) {
                int top = i - h[i][j] + 1;
                maximal_rects.insert({top, l[i][j], i, r[i][j]});
            }
        }
    }

    cout << maximal_rects.size() << endl;
}

int main() {
    // 加速 C++ 的 IO，对付大数据量时很有用哦
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析

时间复杂度: $O(N \times M)$ 我们对整个 $N \times M$ 的矩阵进行了若干次遍历。DP计算 h, l, r 的过程，每一行都只依赖上一行和当前行，所以总共是 $O(N \times M)$ 。最后筛选和计数的循环也是 $O(N \times M)$ 。向 set 中插入一个元素的时间是 $O(\log K)$ ，其中 $K$ 是 set 中元素的数量 ( $K \le N \times M$ )。所以总的时间复杂度是 $O(N \times M \log(NM))$ ，但在大多数情况下，我们可以近似认为是 $O(N \times M)$ ，因为对数因子增长很慢。
空间复杂度: $O(N \times M)$ 我们使用了 grid, h, l, r 四个 $N \times M$ 大小的二维数组来存储矩阵和DP状态。set 也可能在最坏情况下存储 $O(N \times M)$ 个矩形。所以空间复杂度是 $O(N \times M)$ 。

知识点总结

这道题是一个非常经典的二维DP问题，融合了几个重要的思想：

DP状态设计: 核心在于如何为网格中的每个点设计一个能充分描述所需信息的DP状态。这里我们用了 (高度, 左边界, 右边界) 三个量来刻画一个矩形。
降维与分治思想: 将复杂的二维问题，通过逐行处理，转化为一系列更简单的一维问题（计算当前行的临时边界），再将结果合并，是处理这类问题的常用技巧。
极大性判断: 识别出问题的关键约束（“不被包含”），并将其转化为具体的、可编程的检查条件（只检查向下的扩展性）。
数据结构辅助去重: 当算法可能多次识别到同一个目标时，使用 set 或 hash map 等数据结构进行去重，是保证计数准确性的标准做法。

希望这篇题解能帮助你更好地理解这个问题，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！

All-one Matrices - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：从二维到一维的思考转换 ​

第二步：动态规划计算矩形信息 ​

第三步：筛选出“极大”的矩形 ​

第四步：去重计数 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​