最大大小子方阵全1 [英] Maximum size square sub-matrix with all 1s

问题描述

由于二元矩阵，我必须找出最大尺寸子方阵的所有 1 秒。

例如，请考虑下面的二元矩阵：

  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
 

我在网上搜索解决办法，我找到了一个关系，构建一个辅助矩阵：

 如果M [i] [j]为1，则
            S [I] [j]的分钟=（S [i]于[J-1]，S [I-1] [j]时，S [I-1] [J-1]）+ 1
         否则/ *如果M [i] [j]为0 * /
            S [I] [J] = 0
 

1. 其中， M [] [] 是原始矩阵和 S [] [] 是辅助矩阵？
2. 是什么关系意味着什么？
3. ？它有帮助。

解决方案

这是一个典型的动态规划问题。和U如下没有提到整个算法是：

要构造辅助阵列，我们必须做到以下几点：

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

2. 而对于为u提到的其余项目做到以下几点：

    如果M [i] [j]为1，则
       S [I] [j]的分钟=（S [i]于[J-1]，S [I-1] [j]时，S [I-1] [J-1]）+ 1
    否则/ *如果M [i] [j]为0 * /
       S [I] [J] = 0
    

3. 查找S [] []的最大入口，并用它来构造的最大大小方块子矩阵

是什么关系意味着什么？的

要找到最大的广场，我们需要找到不同的方向1秒的最小延伸，并把它加1，形成方形的长度为present情况下结束。

，以便为您的案件S [] []是：

  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] ，它需要留下照顾和顶级direction.However，我们还需要确保有1的透视正方形的左​​上角。 S [I-1] [J-1]，根据定义，包含了一个最大正方形位置i-1，J-1，其左上角，提出了如何向上和向左我们可以得到一个上限。因此，我们需要考虑这一点。

希望这有助于！

Given a binary matrix, I have find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix:

   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

The maximum square sub-matrix with all set bits is

1  1  1
1  1  1
1  1  1

I searched the web for solutions and I found a relation to construct an auxiliary matrix:

 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. Where M[][] is the original matrix and s[][] is the auxiliary matrix?
2. What does this relation signify?
3. And how is it helpful.

解决方案

This is a classic Dynamic Programming problem. And u haven't mentioned the entire algorithm which is as follows:

To construct the auxiliary array we have to do the following:

1. First copy the first row and first column as it is from M[][] to S[][]

2. And for the remaining entries as u mentioned do the following:

    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. Find the maximum entry in S[][] and use it to construct the maximum size square submatrix

What does this relation signify?

To find the maximum square, we need to find the minimum extension of 1s in different directions and add 1 to it to form the length of square ending at present case.

so as for your case s[][] would be:

   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

If we just take minimum of these i.e S[i][j-1], S[i-1][j] , it takes care of left and top direction.However, we also need to make sure that there are 1's in top left corner of perspective square. S[i-1][j-1], by definition, contains a max square at position i-1, j-1, whose top left corner ,puts an upper limit on how up and left we can get. So, we need to consider that as well.

Hope this helps!

这篇关于最大大小子方阵全1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！