概述
我正在尝试用Python实现Maximum Rectangle Algorithm from Dr. Dobbs(清单4).它主要起作用,但是一个特定情况会给出错误的结果,我无法弄清楚原因.
这是我的源代码：
from collections import namedtuple
Point = namedtuple('Point',('X','Y'))
#Y 0 1 2 X
arr = [[0,],#0
[1,#1
[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,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)).
stack.append((y0,w0))
总结
以上是编程之家为你收集整理的python – 最大矩形算法实现全部内容，希望文章能够帮你解决python – 最大矩形算法实现所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群