Алгоритм максимального прямоугольника

Question

Это вопрос о назначении школы. Нам пришлось использовать алгоритм, чтобы найти самый большой возможный прямоугольник с 0s в матрице с 0 и 1 Я выбрал алгоритм грубой силы, поскольку проблема является лишь небольшой проблемой, , но она не работает. Любая помощь/идеи?

'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

Пример:

000000 
000000 
000000 
111000 
111000 
111000 

Это должно дать 18, и это делает. Если я увеличить это матрица 6х10 и я разместить 3х3 подматрицы с 1-х в в lowerleft угол, чем это должно дать мне 42, но только дает мне 30

0000000000 
0000000000 
0000000000 
1110000000 
1110000000 
1110000000 

Answer 1

isFree() глючит. Контуры for никогда не запускаются более одного раза; вы всегда нажимаете либо return True, либо return False.

Answer 2

Для isFree, на первой итерации для петель, это будет либо вернуть True или False, он никогда не получит на второй итерации, таким образом, он будет только когда-либо проверить первую ячейку. (кредит до Armin Rigo's answer, только возможное разъяснение)

Итак, return False должен быть вне цикла.

Кроме того, True и False следует поменять местами вокруг (потому что это бесплатно, когда все 0 s).

Какой прямоугольник ваш код на самом деле возвращения:

Для первого:

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