Задача: 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, чтобы получить количество квадратных подматриц, состоящих из всех единиц.

😎 Решение:

function countSquares($matrix) {
    $m = count($matrix);
    $n = count($matrix[0]);
    $dp = array_fill(0, $m, array_fill(0, $n, 0));
    $count = 0;

    for ($i = 0; $i < $m; $i++) {
        for ($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], min($dp[$i][$j-1], $dp[$i-1][$j-1])) + 1;
                }
                $count += $dp[$i][$j];
            }
        }
    }

    return $count;
}

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