Ctrl K

Самая большая рамка из единиц

Средняя
Дана прямоугольная таблица grid из нулей и единиц. Найдите квадрат наибольшего размера, у которого все клетки на границе — единицы (что внутри, неважно). Верните число клеток в этом квадрате, то есть квадрат длины его стороны. Если в таблице нет ни одной единицы, верните 0. Одна клетка с единицей — тоже квадрат, со стороной 1.
Пример 1
grid=[[1, 1, 1, 0], [1, 0, 1, 1], [1, 1, 1, 1]] → 9

Рамка 3 × 3 в левом верхнем углу целиком из единиц (ноль внутри не мешает) — в ней 9 клеток.

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

Квадрата 2 × 2 нет: в углу ноль. Подходит любая одиночная единица — 1 клетка.

Пример 3
grid=[[0, 0, 0]] → 0

Единиц нет совсем, ответ 0.

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

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