221 Maximal Square

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

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.

思路： 非常简单，公式 if matrix==1 那么 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1 就很清楚了

LC: https://leetcode.com/problems/maximal-square/

jiuzhang: http://www.lintcode.com/en/problem/maximal-square/

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        r, c = len(matrix), len(matrix[0])

        #init dp 2D array
        dp = [[0 if matrix[i][j]=='0' else 1 for j in range(c)] for i in range(r)]

        for i in range(1, r):
            for j in range(1, c):
                if matrix[i][j]=='1':
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
                else:
                    dp[i][j] = 0

        # find the longest square
        res = max([max(i) for i in dp])
        return res**2


so = Solution()
print so.maximalSquare([[1]])