Математика: Операции с матрицами.

Дана матрица a(m,n) из 0 и 1. Найти в ней квадратную подматрицу из одних единиц максимального размера.

В элемент a[i,j] матрицы будем заносить длину максимальной стороны квадрата из единиц, у которого элемент (i,j) есть верхний левый угол (очевидно, что если a[i,j]=0, то квадрат построить нельзя).

Матрицу A будем просматривать по строкам справа налево, снизу вверх.

Предположим, что текущий просматриваемый элемент a[i,j] (все элементы, лежащие в строках с номерами больше i, равно как и все элементы строки i правее a[i,j] считаются уже к этому моменту просмотренными).

Если элемент a[i,j]=0, то его значение остается нулевым. Если же a[i,j]=1, то для того, чтобы найти максимальный размер квадрата из единиц, у которого (i,j) - верхний левый угол, проанализируем уже просмотренные элементы a[i,j+1], a[i+1,j+1], a[i+1,j] - соответственно длины сторон максимальных квадратов с левым углом справа, по диагонали вниз и просто вниз от данного элемента. Квадрат с верхним левым углом (i,j) может протянуться вправо набольше чем на a[i+1,j]+1, вниз - не больше чем на a[i,j+1]+1 и по диагонали не больше чем на a[i+1,j+1]+1. Следовательно, максимальная сторона квадрата есть

a[i,j]=min{a[i,j+1],a[i+1,j],a[i+1,j+1]}+1.

Программа:

MaxDim:=0;{текущая максимальная длина стороны}
for i:=n-1 downto 1 do
for j:=m-1 downto 1 do
if a[i,j]<>0
then begin
a[i,j]:=min(a[i,j+1],a[i+1,j+1],a[i+1,j])+1;
if a[i,j]>MaxDim
then a[i,j]:=MaxDim
end;
writeln('максимальная длина стороны= ',MaxDim);

Вверх по странице, к оглавлению и навигации.