Python在矩阵动态编程中找到了最大的正方形

Question

我有一个矩阵如下(Python(：

matrix = """
...o..o.o
...oo....
...o....o
..o.ooo..
o...o....
.oo......
..o....o.
.oo......
.........
"""

其中"；o"；是一个障碍，我需要找到这个矩阵中最大的正方形。并替换相应的"。"像下面的"x">

"""
xxxo..o.o
xxxoo....
xxxo....o
..o.ooo..
o...o....
.ooxxxx..
..oxxxxo.
.ooxxxx..
...xxxx..
""

在这里发现了类似的问题(SO(，但没有任何帮助。

Answer 1

正如我之前所建议的，如果您可以首先建立一个正确的数据结构来包含所有数量的连续点，然后再从那里开始工作，那么就更容易找到解决方案。下面是展示这一点的示例代码：(第1部分在这里回答，第2部分-留给你练习(这段代码是从另一篇S/O帖子(@AlainT(中采用的，并相应地修改以适应这个问题/格式。(顺便说一句，你的代码样本根本不起作用，也许是格式问题？(

def bigSquare(matrix):
spanSize = [ list(map(len,row.split("o"))) for row in matrix ]

# print([s for ss in spanSize for s in ss if s>0]) # your array of numbers
spans    = [ [c for s in ss
for c in range(s,-1,-1)]
for ss in spanSize
]

#print(f' spans: {spans} ')

result   = (0,0,0,0,0) # area, height, width, top, left

for r,row in enumerate(spans):
for c in range(len(row)):
nextSpans = accumulate( (spanRow[c] for spanRow in spans[r:]),min)
rectSize  = max( [(w*h,h,w) for h,w in enumerate(nextSpans,1)] )
print(r, c, rectSize)

result    = max(result,rectSize+(r,c))
return result[0]   # return the Square Area

if __name__ == '__main__':
matrix =['...o..o.o',
'...oo....',
'...o....o',
'..o.ooo..',
'o...o....',
'.oo......',  # <--- start
'..o....o.',
'.oo......',
'.........']

print(bigSquare(matrix))   # Output: 16 

Answer 2

使用动态编程可以在复杂度为O(n²)的情况下完成。这个想法是，只有当上、左和左上的正方形具有相同的尺寸时，你才会有一个更大的正方形。否则，当前单元格的最大平方只是上面考虑的平方中的最小平方，增加了1。这是代码：

matrix = """
...o..o.o
...oo....
...o....o
..o.ooo..
o........
.oo......
..o....o.
.oo......
.........
"""
matrix = [list(r) for r in matrix.split()]

dp = [[0] * len(matrix) for _ in range(len(matrix))]
# max_square_dim, row, column
max_squares = [(0, None, None)]
for ri, r in enumerate(matrix):
for ci, c in enumerate(r):
dp[ri][ci] = 0 if c == 'o' 
else (1 if ri == 0 or ci == 0 
else min(dp[ri - 1][ci], dp[ri][ci - 1], dp[ri - 1][ci - 1]) + 1)

max_squares = [(dp[ri][ci], ri, ci)] if dp[ri][ci] > max_squares[0][0] 
else (max_squares + [(dp[ri][ci], ri, ci)] if dp[ri][ci] == max_squares[0][0]
else max_squares)

for max_square in max_squares:
for r in matrix[max_square[1] - max_square[0] + 1:max_square[1] + 1]:
r[max_square[2] - max_square[0] + 1:max_square[2] + 1] = ['x'] * max_square[0]

result = 'n'.join([''.join(r) for r in matrix])

print(result)

最后，当您必须用所有x替换最大的正方形时，只需检索最大正方形右下顶点的索引(存储在max_square中(并进行列表替换。

---

EDIT：如果您有多个最大的正方形，而不是声明一个max_square，那么您有一个它们的列表(在更新代码中，我将其重命名为max_squares(。然后，每次遇到与最大尺寸相同的正方形时，只需将其附加到max_squares。但是，请考虑重叠正方形的可能性。