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..
""

在这里发现了类似的问题（所以），但没有任何帮助

Answer 1

它可以使用动态规划以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）并进行列表替换

---

编辑：如果您有多个最大的正方形，而不是声明一个max_square，您有一个它们的列表（在更新代码中，我将其重命名为max_squares）。然后，每次你遇到一个与最大的正方形尺寸相同的正方形，你就把它附加到max_squares上。然而，考虑重叠平方的可能性。

Answer 2

正如我之前所建议的，如果您可以建立一个正确的数据结构，首先包含所有数量的连续点，然后从那里开始工作，那么解决方案就更容易了。下面是示例代码：（第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