Войти Регистрация
Алгоритмы

9. Сколько квадратов из единиц в матрице

Средняя

Дана матрица из нулей и единиц. Посчитайте, сколько в ней квадратных подматриц, целиком заполненных единицами. Квадраты любого размера считаются, включая 1×1.

В работе: Сколько квадратных участков под склад можно выделить на плане, где 1 — свободная клетка.

Пример 1

Ввод
matrix = [[1, 1],
          [1, 1]]
Вывод
5

Четыре квадрата 1×1 и один 2×2.

Пример 2

Ввод
matrix = [[1, 0],
          [1, 1]]
Вывод
3

Только три квадрата 1×1.

Ограничения

  • 1 ≤ строк, столбцов ≤ 300 (в JavaScript — до 1000)
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def count_squares(matrix: list[list[int]]) -> int:
Динамическое программированиеМатрицацельO(n)

Источник: отчёт о Т‑Банке, 2021. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.