Задача: 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 {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int count = 0;

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

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