题解 | 最大子方阵

# -*- coding:utf-8 -*-

class SubMatrix:
    def maxSubMatrix(self, mat, n):
        # 初始化四个预处理矩阵
        right0 = [[0] * n for _ in range(n)]
        right1 = [[0] * n for _ in range(n)]
        down0  = [[0] * n for _ in range(n)]
        down1  = [[0] * n for _ in range(n)]

        # 计算right0和right1(从右往左)
        for i in range(n):
            right0[i][n-1] = 1 if mat[i][n-1] == 0 else 0
            right1[i][n-1] = 1 if mat[i][n-1] == 1 else 0

            for j in range(n - 2, -1, -1):
                if mat[i][j] == 0:
                    right0[i][j] = right0[i][j+1] + 1
                    right1[i][j] = 0
                else:
                    right0[i][j] = 0
                    right1[i][j] = right1[i][j+1] + 1

        # 计算down0和down1(从下往上)
        for j in range(n):
            down0[n-1][j] = 1 if mat[n-1][j] == 0 else 0
            down1[n-1][j] = 1 if mat[n-1][j] == 1 else 0

            for i in range(n - 2, -1, -1):
                if mat[i][j] == 0:
                    down0[i][j] = down0[i+1][j] + 1
                    down1[i][j] = 0
                else:
                    down0[i][j] = 0
                    down1[i][j] = down1[i+1][j] + 1

        # 从大到小检查可能的边长
        for k in range(n, 0, -1):
            for i in range(0, n - k + 1):
                for j in range(0, n - k + 1):
                    if (right0[i][j] >= k and right0[i + k -1][j] >= k and down0[i][j] >= k and down0[i][j + k -1] >= k) or \
                       (right1[i][j] >= k and right1[i + k -1][j] >= k and down1[i][j] >= k and down1[i][j + k -1] >= k):
                        return k
        return 1

def main():
    # 创建矩阵mat [[1,1,1],[1,0,1],[1,1,1]],3
    mat = [[1,1,1],[1,0,1],[1,1,1]]

    mat2 = [
        [1, 1, 1, 1],
        [1, 0, 0, 1],
        [1, 0, 0, 1],
        [1, 1, 1, 0]
    ]

    mat3 = [
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]
    ]

    n = 3

    # 创建SubMatrix类实例
    submatrix = SubMatrix()

    # 调用方法查找到最大子方阵的边长
    maxSubMatrixLength = submatrix.maxSubMatrix(mat,n)

    print(maxSubMatrixLength)

if __name__ == "__main__":
    main()