最大尺寸方形子矩阵,全1

Question

给定一个二进制矩阵,我找出了所有1s 的最大尺寸方形子矩阵.

例如,考虑以下二进制矩阵:

   0  1  1  0  1 
   1  1  0  1  0 
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0

所有设置位的最大平方子矩阵是

1  1  1
1  1  1
1  1  1

我在网上搜索解决方案,然后找到了构建辅助矩阵的关系:

 If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0

1. M[][]原始矩阵在哪里,s[][]是辅助矩阵？
2. 这种关系意味着什么？
3. 它是如何有用的.

Answer 1

这是一个经典的动态编程问题.你还没有提到整个算法如下:

要构造辅助数组,我们必须执行以下操作:

1. 首先复制第一行和第一列,因为它是从M [] []到S [] []

2. 对于你提到的其余条目,请执行以下操作:

    If M[i][j] is 1 then
       S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
    Else /*If M[i][j] is 0*/
       S[i][j] = 0
   

3. 在S [] []中找到最大条目,并使用它来构造最大尺寸的方形子矩阵

这种关系意味着什么？

为了找到最大平方,我们需要在不同方向上找到1的最小扩展,并在其上加1以形成在当前情况下结束的方形长度.

对于你的案例,[] []将是:

   0  1  1  0  1
   1  1  0  1  0
   0  1  1  1  0
   1  1  2  2  0
   1  2  2  3  1
   0  0  0  0  0

如果我们只采用最少这些,即S[i][j-1], S[i-1][j]它会照顾左侧和顶部方向.但是,我们还需要确保透视方块的左上角有1个.根据定义,S [i-1] [j-1]包含位于i-1,j-1的最大平方,其左上角是我们可以获得的向上和向左的上限.所以,我们也需要考虑这一点.

希望这可以帮助!