C++ 中所有 1 的最大正方形子矩阵

在本文中，您将学习如何在 C++ 中找到一个所有元素都为 1 的最大正方形子矩阵。

问题陈述

给定一个二维矩阵，您必须搜索一个所有元素都为 1 的最大尺寸矩阵。

输入格式

一个 n X m 阶的二维矩阵。

输出格式

一个整数，表示最大尺寸矩阵的面积。

这意味着最大尺寸矩阵中所有 1 的总和。

例如解释如下

矩阵是

{{'1', '0', '1', '0', '0'},

{'1', '0', '1', '1', '1'},

{'1', '1', '1', '1', '1'},

{'1', '0', '0', '1', '0'}}

输出

4

最大尺寸矩阵是

{{'1', '1'},

{'1', '1'}}

方法 1：暴力法

让我们举一个例子，在 C++ 中使用暴力法找到全为 1 的最大正方形子矩阵。

输出

说明

上述程序用于查找大小为 n 或 n X n 阶的子矩阵。这是一种暴力法，其主要思想或思维过程是遍历矩阵。首先，取固定大小为 2 的子矩阵，并将其向右滑动，直到它到达矩阵的末尾。如果它们水平到达矩阵的末尾，则将该子矩阵向下移动一步，然后从起始位置再次滑动到矩阵的末尾。它形成一个固定大小为 2 X 2 阶的矩阵。

之后，改变子矩阵的阶数；将其改为3 X 3。再次，对所有不同大小的子矩阵执行相同的过程。当不再生成子矩阵时，它将结束。在这里，您在遍历或滑动矩阵时必须做一件事：检查矩阵中存在的所有元素是否都是 1。如果所有元素都是 1，则将矩阵的大小存储在一个变量中。每次您获得一个大小大于该变量的子矩阵时，您都会使用一个新大小更新变量的值，其中每个大小的矩阵都只包含 1。完成所有这些过程后，打印您存储的变量。它将为您提供所需的输出。此方法可能更优化。它需要更多的时间和空间才能获得结果。

方法 2：使用 Dp 数组

让我们举一个例子，在 C++ 中使用Dp 数组找到全为 1 的最大正方形子矩阵。

输出

说明

为了理解上述程序，我们首先将查看程序中存在的变量。首先是矩阵，即只包含 1 和 0 的输入二维数组。Dp 数组是一个动态数组，用于存储已计算的子问题解决方案，以避免计算中的错误。它有助于优化程序的递归问题。最初，dp 数组中的所有值都设置为 -1，表示尚未计算。整数 i 和 j 是表示矩阵当前行和当前索引的变量。整数 left、right 和 diagonal 变量存储 findMaxSquare 函数中递归调用的结果。maxSize 将跟踪我们的主要输出，即子正方形的最大大小。

函数 findMaxSquare 的基本情况是如果 i 或 j 超出矩阵范围，它将返回零。之后，我们必须在此函数中进行记忆化。如果矩阵中的 i 和 j 已经计算并存储在 dp 表中。它将返回存储的结果。否则，它将递归计算左侧、上方和对角线单元格的影响，并将结果的最小值加 1 存储在 dp 数组中。之后，此函数将返回最终最大正方形的大小。

方法 3：制表法

让我们举一个例子，在 C++ 中使用制表法找到全为 1 的最大正方形子矩阵。

输出

说明

程序中存在的变量是一个矩阵，它是一个只包含 1 和 0 的输入二维数组。Dp 是一个动态数组，用于存储已计算的子问题解决方案，以避免计算中的错误。它有助于优化程序的递归问题。最初，dp 数组中的所有值都设置为 0，表示尚未计算。整数 i 和 j 是表示矩阵当前行和当前索引的变量。整数 left、right 和 diagonal 变量存储结果。

程序检查输入矩阵中的每个单元格。如果单元格包含 '1'，它会计算可以以该单元格结尾的最大正方形的大小，考虑左侧、上方和左上方对角线附近的单元格。它会跟踪找到的最大正方形。最后，函数返回输入矩阵中由 '1' 组成的最大正方形的面积。

结论

以上文章的完美结论如下

暴力法

• 时间复杂度：O((mn)^3)
• 空间复杂度：O(1)

使用 dp 数组

• 时间复杂度：O(mn^2)
• 空间复杂度：O(mn)

制表

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

暴力法仔细检查每个可能的子矩阵，导致时间复杂度大幅增加。另一方面，动态规划技术（自顶向下和自底向上）通过记忆中间结果来优化解决方案，显着降低了时间复杂度。在这些动态规划策略中，自底向上或制表法因其在时间和空间上的卓越效率而脱颖而出。因此，它是解决此问题的首选方法。总之，尽管所有方法都可以解决问题，但采用带制表法的动态规划提供了最有效的解决方案，有效地管理了时间和空间复杂度。