최대 사각형 알고리즘

Question

이것은 학교 과제와 관련된 질문입니다. 가장 큰 사각형을 찾기 위해 알고리즘을 사용해야했습니다. 행렬에서 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

예 :

000000 
000000 
000000 
111000 
111000 
111000 

이 18을 제공해야하고한다. 나는 6X10 매트릭스 으로 증가하고 난 에 lowerleft 코너를 하나의와 3 × 3 행렬을 배치하면 , 그것은 나에게 (42)을 줄 것보다,하지만 나에게 isFree()이 버그가 30

0000000000 
0000000000 
0000000000 
1110000000 
1110000000 
1110000000 

Answer 1

을 제공합니다. for 루프는 두 번 이상 실행되지 않습니다. 항상 return True 또는 return False 중 하나를 누르십시오.

Answer 2

isFree의 경우 for 루프의 첫 번째 반복에서 True 또는 False을 반환 할 것이므로 두 번째 반복에 도달하지 않으므로 첫 번째 셀만 검사합니다. Armin Rigo's answer에 대한 크레딧, 단지 가능한 설명)

따라서 return False은 루프 외부에 있어야합니다. (이 무료이기 때문에 할 때 모든 0들)

은 또한, True 및 False은 주변에 교환해야한다.

첫 번째의 경우 :

111000 
111000 
111000 

두 번째의 경우 :

1110000000 
1110000000 
1110000000 

그래서 코드처럼 보일 것이다 코드가 실제로 반환 직사각형

: (참고 - 내 파이썬은 조금 녹슬 었음)

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