给一个
的0，1矩阵，求它的面积最大的全1子块。
要求
时间。
阅微客栈 » 头脑风暴
算法：求0，1矩阵的最大连续全1块
(12 posts)-
发布于 1 年 之前 #
-
对矩阵做三次扫描, 扫描的次序都是从左到右,从上到下.第一遍将所有为1的元素,依次标一个值,这个值从1开始 例如:
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 2 0 0
0 1 0 0 0 标注成这样 0 3 0 0 0
0 0 0 1 0 0 0 0 4 0
0 0 0 1 0 0 0 0 5 0
第二遍 如果 遇到不为0 的元素, 考虑这个元素以及它周围四个元素中,不为0的元素标，求他们的最小值，并将这些元素通标注为这个最小值 像上面，遇到了１ 那么将 2和3 标注成 1 。就变成下面这样
0 0 0 0 0
0 1 1 0 0
0 1 0 0 0
0 0 0 4 0
0 0 0 4 0
左后一遍 数一下各种数字的个数，最多的，就是最大全1子块的面积发布于 1 年 之前 # -
0 0 0 0 0
0 1 1 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 1 0
标注成
0 0 0 0 0
0 1 2 0 0
0 3 0 0 0
0 0 0 4 0
0 0 0 5 0发布于 1 年 之前 # -
szuxjq
Memberahua同志，不大对吧？这里的“子块”的意思应该是矩阵吧？形状应该是长方形那样的呀，你那个缺个角也算？
发布于 1 年 之前 # -
我不是方的都求出来了，最后把不是方的踢掉，不就行了，踢不是方的不是什么难事吧
发布于 1 年 之前 # -
szuxjq
Memberahua你这样搞出一大片不规则的连续区域，我不晓得怎么往下做哇。。。
发布于 1 年 之前 # -
sandacn
Member分治法，分成4块 1 2 3 4
递归做，找出 1 2 3 4 最大的连续块，然后合并 尝试合并12 13 24 34 1234，
复杂度为T（n） = 4T(n/4) + 5
块的分布：
1 2
3 4发布于 1 年 之前 # -
foo
Member对值为1的位置(x,y)，找到最小的y'，y'<=y，满足(x,y)到(x,y')一段全为1，并记y-y'+1为h(x,y)，然后以h(x,y)为高向两边扩展，找到最左和最右能扩展的位置xleft(x,y),xright(x,y)，宽度w(x,y)=xright(x,y)-xleft(x,y)+1，面积S(x,y)=h(x,y)*w(x,y)
从所有S(x,y)中取最优，所有需要计算的变量通过递推求得，可以做到O(n^2)
发布于 1 年 之前 # -
不错，思路就是这样的。细节上还不够完整
发布于 1 年 之前 # -
szuxjq
Member假设q(a)代表对应坐标a的另一坐标，坐标a和q(a)表示以q(a)为左上角，a为右下角的一个连续全1矩形。这样，对于某一坐标b，可以根据其上方坐标c对应的q(c)和左边坐标d对应的q(d)，来算出b所对应的q(b)。这个想法对不对？
发布于 1 年 之前 # -
BreakDrS
Member1. 对于每点(x,y),记录该点向上最多有多少个1和向左最多有多少个1,递推,O(n^2)
2. 按从上往下，从左往右的顺序求以每个点为右下角的最大矩形，将该矩形数据(长、宽）记录在a[i][j] （动态规划）
3. 求解a[i][j]时，必然已经求出a[i-1][j]，a[i][j-1]，若第一座标(i)表示行号，则新矩形a[i][j]的高度不可能超过a[i-1][j]的高度+1，否则与a[i-1][j]为最大矩形矛盾。 同理宽度不大于a[i][j-1]的宽度+1。 于是得到两个可能的最大矩形。 注意这两个最大矩形不一定能够同时取出，但至少可以取出一个。 从两个当中选取那个较大的，O(1)。
4. 遍历a[i][j]求出面积最大的“最大矩形”
综上为O(n^2)*O(1) = O(n^2)发布于 1 年 之前 # -
lele
Member我的算法只对矩阵做一次行扫描，
00100
10101
01111
行扫描完
00100
10201
01312
并在每行扫描完后根据现有扫描值算出至此为止的最大面积
（用此行中如01312做一系列检验得出值）
如上所例第一行完后最大值为1
第二行后为2第三行为4
得出最后结果发布于 8 月 之前 #
回复
你必须 登录 后发帖。