最大矩形算法

Question

这是一个关于学校作业的问题。 我们必须使用一种算法来找到最大的矩形 在0和1的矩阵中有0 我选择了蛮力算法，因为问题只是个小问题， 但似乎行不通。有什么帮助/想法吗？在

'Determine greatest rectangle'
def determineBiggest(self):
    best_ll = [0,0]
    best_ur = [-1,-1]
    for llx in range(0,len(self.verkaveling)):
        for lly in range(0,len(self.verkaveling[0])):
            for urx in range(llx, len(self.verkaveling)):
                for ury in range(lly, len(self.verkaveling[0])):
                    if(self.grootte(llx,lly,urx,ury) > self.size(best_ll[0],best_ll[1],best_ur[0],best_ur[1])) and (self.isFree(llx,lly,urx,ury)):
                        best_ll[0]=llx
                        best_ll[1]=lly
                        best_ur[0]=urx
                        best_ur[1]=ury
    print self.size(best_ll[0],best_ll[1],best_ur[0],best_ur[1])                      
'Determine size of rectangle'                       
def grootte(self,a,b,c,d):
    if(a > c) or (b > d):
        return 0
    else:
        return (c-a+1)*(d-b+1)
'Check if rectangle is fully free'
def isFree(self,a,b,c,d):
    for x in range(a, c):
        for y in range(b, d):
            if self.verkaveling[x][y] == "0":
                return False
            else:
                return True

来源：used source

示例：

^{pr2}$

这应该是18，它确实是。 如果我把它增加到6x10矩阵 我放了一个3x3的子矩阵 最下面的角落，比那应该给我的 42岁，但只有30岁

0000000000
0000000000
0000000000
1110000000
1110000000
1110000000

Answer 1

对于isFree，在For循环的第一次迭代中，它将返回True或{}，它永远不会到达第二次迭代，因此它只检查第一个单元格。（归功于Armin Rigo's answer，只是一个可能的澄清）

所以，return False需要在循环之外。在

另外，True和{}应该交换（因为当所有0时，是空闲的）。在

代码实际返回的矩形：

首先：

111000
111000
111000

第二种情况：

^{pr2}$

因此，代码应该类似于：（注意，我的Python有点生疏）

def isFree(self,a,b,c,d):
    for x in range(a, c):
        for y in range(b, d):
            if self.verkaveling[x][y] == "1":
                return False
    return True

Answer 2

这辆isFree()是一辆小车。for循环永远不会运行一次以上；您总是点击return True或{}。在