最大尺寸方形子矩阵,全部为1
给定一个二进制矩阵,我找出了全1
s的最大尺寸方形子矩阵。
例如,考虑以下二进制矩阵:
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
- 其中
M[][]
是原始矩阵,s[][]
是辅助矩阵? - 这种关系意味着什么?
- 它是如何有用的。
这是一个经典的动态编程问题。 你还没有提到整个算法如下:
要构造辅助数组,我们必须执行以下操作:
-
首先复制第一行和第一列,因为它是从M [] []到S [] []
-
对于你提到的其余条目,请执行以下操作:
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
-
在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的最大平方,其左上角是我们可以获得的向上和向左的上限。 所以,我们也需要考虑这一点。
希望这可以帮助!
您可以在线性时间内完成此操作。
声明:我可以在线性时间内构建一个数据结构,让我可以在恒定时间内检查任意矩形是否满是1。
certificate:部分金额; 取S[i][j]
为(i, j)
左上方1的总数。 (a,b)
和(c,d)
之间的矩形中的数目(a,b)
(c,d)
上方和左侧,是S[c][d] + S[a][b] - S[a][d] - S[b][c]
。
现在它是对arrays的简单扫描:
size = 1; For i = 0 to m-size { For j = 0 to n-size { If S[i+size][j+size] - S[i][j+size] - S[i+size][j] + S[i][j] == size*size { size++; j--; continue; } } }
最后, size
比最大的1满方形大1。
您可以构建一个额外的递归函数,它将当前行和col作为参数,并从中查找任意大小的正方形。
从你的其他函数,aftter额外函数返回一个值,你必须进行2次调用:一个来自(row,col + 1),另一个来自(row + 1,col)。
这是一个回溯用法,我们检查所有选项。