面试题 17.23. 最大黑方阵

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1:

输入:
[
  [1,0,1],
  [0,0,1],
  [0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵

示例 2:

输入:
[
  [0,1,1],
  [1,0,1],
  [1,1,0]
]
输出: [0,0,1]

提示：

• matrix.length == matrix[0].length <= 200

Python 解答：
1.动态规划

class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        dp = [[[0 for k in range(2)] for i in range(len(matrix[0]))] for j in range(len(matrix))]
        if matrix[len(matrix)-1][len(matrix[0])-1]:
            for k in range(2):
                dp[len(matrix)-1][len(matrix[0])-1][k] = 0
        else:
            for k in range(2):
                dp[len(matrix)-1][len(matrix[0])-1][k] = 1

        for i in range(len(matrix)-2, -1, -1):
            if matrix[i][len(matrix[0])-1]:
                for k in range(2):
                    dp[i][len(matrix[0])-1][k] = 0
            else:
                dp[i][len(matrix[0])-1][0] = 1
                dp[i][len(matrix[0])-1][1] =  dp[i+1][len(matrix[0])-1][k]+1  

        for j in range(len(matrix[0])-2, -1, -1):
            if matrix[len(matrix)-1][j]:
                for k in range(2):
                    dp[len(matrix)-1][j][k] = 0
            else:
                dp[len(matrix)-1][j][1] =  1
                dp[len(matrix)-1][j][0] =  dp[len(matrix)-1][j+1][0]+1       

        for i in range(len(matrix)-2, -1, -1):
            for j in range(len(matrix[0])-2, -1, -1):
                if matrix[i][j]:
                    dp[i][j][0] = 0
                    dp[i][j][1] = 0
                else:
                    dp[i][j][0] = dp[i][j+1][0]+1
                    dp[i][j][1] = dp[i+1][j][1]+1
        max_long = 0
        result = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                long = min(dp[i][j][0], dp[i][j][1])
                for size in range(long, 0, -1):
                    if size > max_long and dp[i][j+size-1][1] >= size and dp[i+size-1][j][0] >= size:           
                        max_long = size
                        result = [i, j, size]
        return result