1277. Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

Count Square Submatrices with All Ones - LeetCode

 

 

Input: matrix

[

[0,1,1,1],  

[1,1,1,1],

[0,1,1,1]

]

 

매트릭스에 정사각형이 몇개나 있나 계산하는 문제이다.

dp를 사용하면 되는데...

 

dp는 현재위치를 포함하여 최대 정사각형의 크기를 저장해야 한다. 

 

# matrix
[0, 1, 1, 1]
[1, 1, 1, 1]
[0, 1, 1, 1]
----

# dp_arr
# matrix의 (0,1) 자리가 1일 경우
(1, 2)
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
-----
(1, 3)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
-----
(1, 4)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
-----
(2, 1)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 0, 0, 0]
[0, 0, 0, 0, 0]
-----
(2, 2)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 0, 0]
[0, 0, 0, 0, 0]
-----
# 여기서는 주변이 전부 1인데, 모두 사각형이므로 이중에 최소값은 1이고, 거기다 1을 더한다.
# 2의 의미는 1,2 사이즈의 정사각형을 만드는데 해당 위치가 2번 사용되었다는 의미로 볼 수도 있다.
(2, 3)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 0]
[0, 0, 0, 0, 0]
-----
(2, 4)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 2]
[0, 0, 0, 0, 0]
-----
(3, 2)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 2]
[0, 0, 1, 0, 0]
-----
(3, 3)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 2]
[0, 0, 1, 2, 0]
-----
(3, 4)
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 2]
[0, 0, 1, 2, 3]
-----
[0, 0, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 1, 1, 2, 2]
[0, 0, 1, 2, 3]

 

 

class Solution(object):
    def countSquares(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        
        
        dp_arr = [[0 for j in range(len(matrix[0])+1)] for i in range(len(matrix)+1)]
        
        #dp_arr[0][1] = 1
        for d in matrix:
            print(d)
            
        def print_mat(matrix):
            for d in matrix:
                print(d)
            print("-----")    
        print("----")
        res = 0
        for i in range(1, len(dp_arr), 1):
            for j in range(1, len(dp_arr[0]), 1):
                #dp_arr[i][j] = sum(dp_arr[:i+1][:j+1])
                
                if matrix[i-1][j-1] == 1:
                    #print(i,j)
                    dp_arr[i][j] = min(dp_arr[i-1][j], dp_arr[i][j-1], dp_arr[i-1][j-1]) + 1
                    #print_mat(dp_arr)
                    res += dp_arr[i][j]
                
        
        #for d in dp_arr:
        #    print(d)
        
        return res