IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

> Matritsa
-programmer-
сообщение 24.11.2005 21:49
Сообщение #1


Гость






дана матрица из 0 и 1 в
данной матрицы найти максимальную подматрицу состоящую из 0
Так вот проблема в чем
каждый элемент матрицы посещается не более 1 раза
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
virt
сообщение 25.11.2005 20:19
Сообщение #2


Знаток
****

Группа: Пользователи
Сообщений: 419
Пол: Мужской

Репутация: -  6  +


program max_square_podmatr;
const max_n = 20;
var a : array[0..max_n,0..max_n]of byte;
i,j,n,m : integer;
sc : integer;
max : integer;

function min(a,b : integer) : integer;
begin
if a < b then min := a else min := b;
end;

begin
readln(n,m);
fillchar(a,sizeof(a),0);
max := 0;
for i := 1 to n do
for j := 1 to m do
begin
read(sc);
if sc = 1 then a[i,j] := 0 else
begin
a[i,j] := min (a[i - 1,j],a[i,j - 1]);
a[i,j] := min (a[i,j],a[i - 1,j - 1]) + 1;
end;
if a[i,j] > max then max := a[i,j]
end;
writeln(max * max);
end.


сложность O(n^2)
находит максимальный квадрат.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 14.07.2025 0:32
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"