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) 中采用的，并相应地修改以适应这个 question/format . （顺便说一句 - 您的代码示例根本无法运行，可能是格式问题？）

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。但是，请考虑重叠方块的可能性。

Python求矩阵动态规划中最大的平方

Python find the largest square in the matrix dynamic programming

python

algorithm

dynamic-programming