Python find the largest square in the matrix dynamic programming

Question

I have a matrix as follows (Python) :

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

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

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

You could build up a matrix containing the no. of consecutive dots, then it will be easier to do the measurement. Could you show us what you got so far? — Daniel Hao, Dec 24 '20 at 16:06
@DanielHao the second part, is it doable with my code (link above) ? — Mahi008, Dec 24 '20 at 16:54
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/226397/discussion-between-mahi008-and-daniel-hao). — Mahi008, Dec 24 '20 at 17:33
@DanielHao It's because the website uses python 2.7, and my code is 3 and above, I use the site only to host my code, not to run. try running the code on your machine — Mahi008, Dec 24 '20 at 17:44
this is what i had from the beginning :), the only missing part is to replace square "." with "x"(like the example above in my question), thats where I'm stuck — Mahi008, Dec 24 '20 at 18:02

Daniel Hao · Answer 1 · 2020-12-24T16:30:47.640

As I suggested earlier, it's easier to work out the solution if you could build up a right data structure to contain all number of consecutive dots first, then work from there. Here is the sample code to show this: (part1 answer here, part 2- leave as your exercise) This code is adopted from another S/O posts (@AlainT), and modify to suite this question/format accordingly. (BTW - your code sample did not work at all, maybe the format issue?)

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

Marco Luzzara · Accepted Answer · 2020-12-25T09:53:44.737

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)

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.

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.

It works thanks but what happens if I have multiple(BIG) squares of same size ?, can I be able to highlight separately depending on its position(top, bottom) etc.. ? — Mahi008, Dec 25 '20 at 07:54
Did not think about multiple squares, see the edit and new code. — Marco Luzzara, Dec 25 '20 at 09:55
Great ! just one last question though, If I want to select the (top-left) square between two squares then I should go for `max_squares[0]` right ? — Mahi008, Dec 25 '20 at 10:05
Exactly, the matrix is visited row by row from top, and column by column from left. — Marco Luzzara, Dec 25 '20 at 10:14

Python find the largest square in the matrix dynamic programming

2 Answers2

Linked