最大矩形算法實現

我試圖用Python實現Maximum Rectangle Algorithm from Dr. Dobbs（清單四）。它主要工作，但一個具體的情況給出錯誤的結果，我不明白爲什麼。最大矩形算法實現

這裏是我的源代碼：

from collections import namedtuple 

Point = namedtuple('Point', ('X', 'Y')) 

#Y  0 1 2  X 
arr = [[0, 0, 0, ], #0 
     [1, 0, 0, ], #1 
     [0, 0, 1, ], #2 
     ] 

def area(ll, ur): 
    if (ll.X < 0) or (ll.Y < 0) or (ur.X < 0) or (ur.Y < 0): 
     return 0. 
    return ((ur.X - ll.X) + 1) * ((ur.Y - ll.Y) + 1) 

def update_cache(a, c, x): 
    M = len(a[0]) 
    N = len(a) 
    for y in range(M): 
     if a[x][y] == 0: 
      c[y] = c[y] + 1 
     else: 
      c[y] = 0 

def mrp(a): 
    best_ll = Point(-1, -1) 
    best_ur = Point(-1, -1) 
    M = len(a[0]) 
    N = len(a) 
    c = [0 for x in range(M + 1)] 
    stack = [] 
    for x in range(N-1, -1, -1): 

     update_cache(a, c, x)   
     width = 0 
     for y in range(M + 1): 
      if c[y] > width: 
       stack.append((y, width))     
       width = c[y] 
      if c[y] < width: 
       while True: 
        y0, w0 = stack.pop() 
        if (width * (y - y0)) > area(best_ll, best_ur): 
         best_ll = Point(x, y0) 
         best_ur = Point(x + width - 1, y - 1) 
        width = w0 
        if (c[y] >= width): 
         break 
       width = c[y] 
       if width == 0: 
        stack.append((y0, width)) 
    return best_ll, best_ur

而這裏的結果：

>>> mrp(arr) 
(Point(X=0, Y=0), Point(X=1, Y=2))

正如你所看到的，第一點是錯誤的，但我想不通的地方，爲什麼它出錯。更改arr會給出正確的結果。

編輯：我注意到我已經改變了數組的值與文章相比。這改變了update_cache中的比較。 0 =清除，1 =保留。我正在尋找結果（Point（X = 0，Y = 1），Point（X = 1，Y = 2））。

來源

2011-12-29 Harriv

相關：[查找包含在N×N個二進制矩陣只有零最大矩形]（http://stackoverflow.com/questions/2478447/find-largest -rectangle-containing-only-zeros-in-an-nn-binary-matrix） – jfs 2011-12-29 02:54:21

如果它對任何人有任何用處，請使用基於此和Dr.Dobbs文章的Javascript實現：http://www.codinghands.co。英國/博客/ 2013/02/JavaScript的執行，OMN-最大矩形算法/ – codinghands 2013-02-23 18:03:03

最後stack.append應該是：

stack.append((y0, w0))

來源

2012-01-03 06:25:56 Harriv

最大矩形算法實現

回答

相關問題