# -*- coding: utf-8 -*-
# @Author  : LG

"""
执行用时：84 ms, 在所有 Python3 提交中击败了93.21% 的用户
内存消耗：14.5 MB, 在所有 Python3 提交中击败了27.86% 的用户

解题思想：

"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        m, n = len(matrix), len(matrix[0])
        max_ = 0
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            dp[i][0] = int(matrix[i][0])
            max_ = max(dp[i][0], max_)

        for j in range(1, n):
            dp[0][j] = int(matrix[0][j])
            max_ = max(dp[0][j], max_)

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

                max_ = max(dp[i][j], max_)
        return max_**2


"""
执行用时：120 ms, 在所有 Python3 提交中击败了30.10% 的用户
内存消耗：14.4 MB, 在所有 Python3 提交中击败了61.68% 的用户

解题思路：
    整理代码后，效率变低，但是逻辑上更顺畅
"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        m, n = len(matrix), len(matrix[0])
        max_ = 0
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

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

                max_ = max(dp[i+1][j+1], max_)
        return max_**2
# -*- coding: utf-8 -*-
# @Author  : LG

"""
执行用时：84 ms, 在所有 Python3 提交中击败了93.21% 的用户
内存消耗：14.5 MB, 在所有 Python3 提交中击败了27.86% 的用户

解题思想：

"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        m, n = len(matrix), len(matrix[0])
        max_ = 0
        dp = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            dp[i][0] = int(matrix[i][0])
            max_ = max(dp[i][0], max_)

        for j in range(1, n):
            dp[0][j] = int(matrix[0][j])
            max_ = max(dp[0][j], max_)

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

                max_ = max(dp[i][j], max_)
        return max_**2


"""
执行用时：120 ms, 在所有 Python3 提交中击败了30.10% 的用户
内存消耗：14.4 MB, 在所有 Python3 提交中击败了61.68% 的用户

解题思路：
    整理代码后，效率变低，但是逻辑上更顺畅
"""
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        m, n = len(matrix), len(matrix[0])
        max_ = 0
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

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

                max_ = max(dp[i+1][j+1], max_)
        return max_**2
# -*- coding: utf-8 -*- # @Author  : LG 执行用时：84 ms, 在所有 Python3 提交中击败了93.21% 的用户 内存消耗：14.5 MB, 在所有 Python3 提交中击败了27.86% 的用户  解题思想： 执行用时：120 ms, 在所有 Python3 提交中击败了30.10% 的用户 内存消耗：14.4 MB, 在所有 Python3 提交中击败了61.68% 的用户  解题思路：     整理代码后，效率变低，但是逻辑上更顺畅