Задана таблица N*M, которая состоит из 0 и 1.Найти квадрат максимального размера из единиц.
По рисунку сразу видно что максимальным квадратом будет являться квадрат у которой сторона равна трем.
Составим таблицу ответов,на конкретном примере приведенном выше,ограничивая с двух боков нулями:
Как составляли таблицу:
1)Берем первый элемент(a[1,1]) и смотрим сколько способов есть в составлении квадрата(если это единица). Ответ записываем под таким же номером в массив b[i,j];
2)Если попался ноль следовательно записываем в таблицу ответов ноль).
3)Берем след. элемент это тоже единица. Ответ 1.
...
4)У нас попалась такая ситуация:
Вместо вопроса запишем в таблицу ответов 2.
Код:
for i:=1 to n do
for j:=1 to m do
if a[i,j]=0 then b[i,j]:=0
else b[i,j]:=min(min(b[i-1,j],b[i-1,j-1]),b[i,j-1])+1;
{далле находим максимальный элемент в нашем массиве,это и будет наш ответ на задачу}Ну как-то так)
