на рис. 1. 1 1
на рис. 1.
1 1 1 1 1 1
0 1 1 1 0 1
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 0 1
Рис. 1.
Положение любого квадратного блока может быть определено его размером и положением одного из его углов.
Пусть T(i, j) есть функция, значение которой соответствует размеру максимального квадратного блока, состоящего из одних единиц, правый нижний угол которого расположен в позиции (i, j). Функция T(i, j) вычисляет элемент таблицы B[i, j]. Для примера на рис. значения T(i, j) будут иметь вид
i\j 1 2 3 4 5 6
1 1 1 1 1 1 1
2 0 1 2 2 0 1
3 1 1 2 3 1 1
4 1 2 0 1 2 2
5 1 0 1 1 0 1
Таким образом, наша задача свелась к вычислению максимального значения функции Т при всевозможных значениях параметров i и j. Этой функции может быть поставлена в соответствие таблица размера N*M.
Определим сначала значения элементов таблицы В, расположенных в первой строке и в первом столбце. Получим:
В(1, 1) = А[1, 1],
В(1, j) = А[1, j] при j?2,
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
