时间戳

首页 > 解决方案 > Python在矩阵动态规划中找到最大的正方形

python - Python在矩阵动态规划中找到最大的正方形

问题描述

我有一个矩阵如下（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），但没有任何帮助。

标签： pythonalgorithmdynamic-programming

解决方案

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

推荐阅读