Максимальный квадрат дп на той же матрице

Question

Вопрос о максимальном квадрате в https://leetcode.com/problems/maximal-square/description/ легко решить с помощью DP. но вместо того, чтобы создать новую матрицу, я изменил исходную, но этот подход не удался с контрольным примером № 64, пожалуйста, проверьте мой следующий код и помогите мне определить недостающую точку.

def maximalSquare(self, matrix: List[List[str]]) -> int:

    for x in range(1,len(matrix)):
        for y in range(1,len(matrix[x])):
            if matrix[x][y] == '1':
                matrix[x][y] = str(int(min( matrix[x-1][y], matrix[x][y-1], matrix[x-1][y-1]))+1)

    return int(max([max(x) for x in matrix])) ** 2 if matrix else 0

Answer 1

Полагаю, вы не разбираетесь с угловыми делами. Для меня этот код работает нормально с небольшими изменениями. Кроме того, это будет работать немного медленно.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        m, n, res = len(matrix), len(matrix[0]), 0
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0) and (matrix[i][j] == '1'):
                    res = max(res, 1)
                elif int(matrix[i][j]) == 1:
                    matrix[i][j] = min(int(matrix[i-1][j]), int(matrix[i][j-1]), int(matrix[i-1][j-1])) + 1
                    res = max(res, matrix[i][j])
        return res ** 2

При переборе первой строки или первого столбца формула для dp (i, j) проверяет значения за пределами границ. Сдвиг всего dp вправо и вниз на 1 и добавление отступов 0 к 1-й строке и 1-му столбцу делает формулу работающей без проверки границ.