Ctrl K

Прямоугольники из одних единиц

Средняя
Дана таблица grid из нулей и единиц. Посчитайте, сколько в ней прямоугольных областей (со сторонами вдоль строк и столбцов), в которых **все** клетки равны 1. Прямоугольники с разными границами считаются разными, даже если вложены друг в друга.
Пример 1
grid=[[1, 1], [1, 0]] → 5

Три клетки 1×1, одна полоска 1×2 в верхней строке и одна 2×1 в левом столбце — всего 5.

Пример 2
grid=[[1, 1, 1]] → 6

Три клетки, две полоски длины 2 и одна длины 3 — 6 прямоугольников.

Пример 3
grid=[[0, 1], [1, 1]] → 5
Ограничения
  • 1 ≤ число строк, число столбцов ≤ 150
  • grid[i][j] — 0 или 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый большой горящий блок СложнаяДальние прыжки по полю СложнаяСумма минимумов отрезков СредняяДерево из произведений листьев СредняяКого видно в строю Средняя
загружаем Python…
Вход
grid=[[1, 1], [1, 0]]
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 93 теста на сервере, включая скрытые.