0

这是关于学校作业的问题。我们必须使用一种算法来在具有 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

来源：使用的来源

例子：

000000
000000
000000
111000
111000
111000

这应该给出 18 并且确实如此。如果我将它增加到一个 6x10 矩阵并在左下角放置一个 1 的 3x3 子矩阵，那应该给我 42，但只给我 30

0000000000
0000000000
0000000000
1110000000
1110000000
1110000000
4

2 回答 2

3

这isFree()是越野车。for 循环永远不会运行超过一次；你总是按return True或return False。

于 2013-05-06T18:04:34.607 回答
1

对于isFree，在 for 循环的第一次迭代中，它将返回True或False，它永远不会进入第二次迭代，因此它只会检查第一个单元格。（归功于Armin Rigo的回答，只是一个可能的澄清）

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

此外，True并且False应该交换周围（因为当所有s 时它是0免费的）。

您的代码实际返回的是哪个矩形：

为了第一：

111000
111000
111000

对于第二个：

1110000000
1110000000
1110000000

所以，代码应该是这样的：（注意——我的 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
于 2013-05-06T18:15:38.907 回答