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

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