Python 求矩阵动态规划中最大的平方 [英] Python find the largest square in the matrix dynamic programming

问题描述

我有一个矩阵如下(Python):

I have a matrix as follows (Python) :

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

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

where "o" is an obstacle and I need to find the biggest square in this matrix. and replace corresponding '.' with 'x' like below

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

在这里找到了类似的问题(SO)，但没有任何帮助.

found similar questions here(SO), but nothing helped.

推荐答案

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

It can be done with a complexity of O(n²) using dynamic programming. The idea is that you have a bigger square only when the up, the left and the up-left squares have the same dimension. Otherwise the max square of the current cell is just the smallest square among the squares considered above, increased by 1. Here is the code:

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) 并进行列表替换.

In the end, when you have to replace the biggest square with all xs, you simply retrieve the indexes of the bottom-right vertex of the max square (stored in max_square) and do a list substitution.

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

EDIT: in case you have multiple biggest square, instead of declaring a single max_square, you have a list of them (in the update code I renamed it to max_squares). Then, every time you encounter a square with the same dimension as the max one, you just append it to the max_squares. However, consider the possibility of overlapping squares.

这篇关于Python 求矩阵动态规划中最大的平方的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！