Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium

Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.

Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

👨‍💻 Алгоритм:

1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов.

2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.

😎 Решение:

class Solution {
    func countSquares(_ matrix: [[Int]]) -> Int {
        let m = matrix.count, n = matrix[0].count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        var count = 0

        for i in 0..<m {
            for j in 0..<n {
                if matrix[i][j] == 1 {
                    if i == 0 || j == 0 {
                        dp[i][j] = 1
                    } else {
                        dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
                    }
                    count += dp[i][j]
                }
            }
        }

        return count
    }
}

Ставь 👍 и забирай 📚 Базу знаний