Maximal Square

Question

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Example For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Thoughts

如果matrix[i][j]为1， dp[i][j]的值只与

• 上dp[i-1][j]
• 左dp[i][j-1]
• 左上dp[i-1][j-1]

有关

test cases:

• 全为0
• 全为1

注意初始化的时候的值

Solution

class Solution:
    #param matrix: a matrix of 0 and 1
    #return: an integer
    def maxSquare(self, matrix):
        # write your code here
        if not matrix:
            return 0
        rowNum = len(matrix)
        colNum = len(matrix[0])
        dp = [[0 for i in range(colNum)] for j in range(rowNum)]
        result = 0

        for i in range(rowNum):
            dp[i][0] = matrix[i][0]
            if dp[i][0] > 0:
                result = 1

        for j in range(colNum):
            dp[0][j] = matrix[0][j]
            if dp[0][j] > 0:
                result = 1

        for i in range(1, rowNum):
            for j in range(1, colNum):
                if matrix[i][j]:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    if dp[i][j] >= result:
                        result = dp[i][j]
                else:
                    dp[i][j] = 0

        return result ** 2